src/code/seq.lisp

   1 ;;;; generic SEQUENCEs
   2 ;;;;
   3 ;;;; KLUDGE: comment from original CMU CL source:
   4 ;;;;   Be careful when modifying code. A lot of the structure of the
   5 ;;;;   code is affected by the fact that compiler transforms use the
   6 ;;;;   lower level support functions. If transforms are written for
   7 ;;;;   some sequence operation, note how the END argument is handled
   8 ;;;;   in other operations with transforms.
   9
  10 ;;;; This software is part of the SBCL system. See the README file for
  11 ;;;; more information.
  12 ;;;;
  13 ;;;; This software is derived from the CMU CL system, which was
  14 ;;;; written at Carnegie Mellon University and released into the
  15 ;;;; public domain. The software is in the public domain and is
  16 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
  17 ;;;; files for more information.
  18
  19 (in-package "SB!IMPL")
  20 \f
  21 ;;;; utilities
  22
  23 (defun %check-generic-sequence-bounds (seq start end)
  24   (let ((length (sb!sequence:length seq)))
  25     (if (<= 0 start (or end length) length)
  26         (or end length)
  27         (sequence-bounding-indices-bad-error seq start end))))
  28
  29 (eval-when (:compile-toplevel :load-toplevel :execute)
  30   (defparameter *sequence-keyword-info*
  31     ;; (name default supplied-p adjustment new-type)
  32     `((count nil
  33              nil
  34              (etypecase count
  35                (null (1- most-positive-fixnum))
  36                (fixnum (max 0 count))
  37                (integer (if (minusp count)
  38                             0
  39                             (1- most-positive-fixnum))))
  40              (mod #.sb!xc:most-positive-fixnum))
  41       ;; Entries for {start,end}{,1,2}
  42       ,@(mapcan (lambda (names)
  43                   (destructuring-bind (start end length sequence) names
  44                     (list
  45                      `(,start
  46                        0
  47                        nil
  48                        ;; Only evaluate LENGTH (which may be expensive)
  49                        ;; if START is non-NIL.
  50                        (if (or (zerop ,start) (<= 0 ,start ,length))
  51                            ,start
  52                            (sequence-bounding-indices-bad-error ,sequence ,start ,end))
  53                        index)
  54                      `(,end
  55                        nil
  56                        nil
  57                        ;; Only evaluate LENGTH (which may be expensive)
  58                        ;; if END is non-NIL.
  59                        (if (or (null ,end) (<= ,start ,end ,length))
  60                            ;; Defaulting of NIL is done inside the
  61                            ;; bodies, for ease of sharing with compiler
  62                            ;; transforms.
  63                            ;;
  64                            ;; FIXME: defend against non-number non-NIL
  65                            ;; stuff?
  66                            ,end
  67                            (sequence-bounding-indices-bad-error ,sequence ,start ,end))
  68                        (or null index)))))
  69                 '((start end length sequence)
  70                   (start1 end1 length1 sequence1)
  71                   (start2 end2 length2 sequence2)))
  72       (key nil
  73            nil
  74            (and key (%coerce-callable-to-fun key))
  75            (or null function))
  76       (test #'eql
  77             nil
  78             (%coerce-callable-to-fun test)
  79             function)
  80       (test-not nil
  81                 nil
  82                 (and test-not (%coerce-callable-to-fun test-not))
  83                 (or null function)))))
  84
  85 (sb!xc:defmacro define-sequence-traverser (name args &body body)
  86   (multiple-value-bind (body declarations docstring) (parse-body body t)
  87     (collect ((new-args)
  88               (new-declarations)
  89               ;; Things which are definitely used in any code path.
  90               (rebindings/eager)
  91               ;; Things which may be used/are only used in certain
  92               ;; code paths (e.g. length).
  93               (rebindings/lazy))
  94       (dolist (arg args)
  95         (case arg
  96           ;; FIXME: make this robust.  And clean.
  97           ((sequence sequence1 sequence2)
  98            (let* ((length-var (ecase arg
  99                                 (sequence  'length)
 100                                 (sequence1 'length1)
 101                                 (sequence2 'length2)))
 102                   (cache-var (symbolicate length-var '#:-cache)))
 103              (new-args arg)
 104              (rebindings/eager `(,cache-var nil))
 105              (rebindings/lazy
 106               `(,length-var (truly-the
 107                              index
 108                              (or ,cache-var (setf ,cache-var (length ,arg))))))))
 109           ((function predicate)
 110            (new-args arg)
 111            (rebindings/eager `(,arg (%coerce-callable-to-fun ,arg))))
 112           (t
 113            (let ((info (cdr (assoc arg *sequence-keyword-info*))))
 114              (cond (info
 115                     (destructuring-bind (default supplied-p adjuster type) info
 116                       (new-args `(,arg ,default ,@(when supplied-p (list supplied-p))))
 117                       (rebindings/eager `(,arg ,adjuster))
 118                       (new-declarations `(type ,type ,arg))))
 119                    (t (new-args arg)))))))
 120       `(defun ,name ,(new-args)
 121          ,@(when docstring (list docstring))
 122          ,@declarations
 123          (symbol-macrolet (,@(rebindings/lazy))
 124            (let* (,@(rebindings/eager))
 125              (declare ,@(new-declarations))
 126              ,@body))))))
 127
 128 ;;; SEQ-DISPATCH does an efficient type-dispatch on the given SEQUENCE.
 129 ;;;
 130 ;;; FIXME: It might be worth making three cases here, LIST,
 131 ;;; SIMPLE-VECTOR, and VECTOR, instead of the current LIST and VECTOR.
 132 ;;; It tends to make code run faster but be bigger; some benchmarking
 133 ;;; is needed to decide.
 134 (sb!xc:defmacro seq-dispatch
 135     (sequence list-form array-form &optional other-form)
 136   `(if (listp ,sequence)
 137        (let ((,sequence (truly-the list ,sequence)))
 138          (declare (ignorable ,sequence))
 139          ,list-form)
 140        ,@(if other-form
 141              `((if (arrayp ,sequence)
 142                    (let ((,sequence (truly-the vector ,sequence)))
 143                      (declare (ignorable ,sequence))
 144                      ,array-form)
 145                    ,other-form))
 146              `((let ((,sequence (truly-the vector ,sequence)))
 147                  (declare (ignorable ,sequence))
 148                  ,array-form)))))
 149
 150 ;; Same as above, but don't assume that ARRAYP implies VECTORP,
 151 ;; and test EXTENDED-SEQUENCE-P if three cases are allowed.
 152 ;; Signal a type error for non-sequences.
 153 ;; This is for dispatching within sequence functions that have
 154 ;; the EXPLICIT-CHECK attribute on at least their sequence arg(s).
 155 (eval-when (:compile-toplevel)
 156 (sb!xc:defmacro seq-dispatch-checking
 157     (sequence list-form vector-form &optional (other-form nil other-form-p))
 158   `(cond ((listp ,sequence)
 159           (let ((,sequence (truly-the list ,sequence)))
 160             (declare (ignorable ,sequence))
 161             ,list-form))
 162          ((vectorp ,sequence)
 163           (let ((,sequence (truly-the vector ,sequence)))
 164             (declare (ignorable ,sequence))
 165             ,vector-form))
 166          ,@(cond ((not other-form-p)
 167                   `((t
 168                      (sb!c::%type-check-error ,sequence '(or list vector)
 169                                               nil))))
 170                  (other-form
 171                   `(((extended-sequence-p ,sequence)
 172                      (let ((,sequence (truly-the extended-sequence ,sequence)))
 173                        (declare (ignorable ,sequence))
 174                        ,other-form))
 175                     (t
 176                      (sb!c::%type-check-error/c
 177                       ,sequence 'sb!kernel::object-not-sequence-error nil)))))))
 178
 179 ;;; Like SEQ-DISPATCH-CHECKING, but also assert that OTHER-FORM produces
 180 ;;; a sequence. This assumes that the containing function declares its
 181 ;;; result to be explicitly checked,
 182 ;;; and that the LIST and VECTOR cases never fail to return a sequence.
 183 (sb!xc:defmacro seq-dispatch-checking=>seq
 184     (sequence list-form vector-form other-form)
 185   `(seq-dispatch-checking ,sequence ,list-form ,vector-form
 186                           (the sequence (values ,other-form)))))
 187
 188 (sb!xc:defmacro %make-sequence-like (sequence length)
 189   "Return a sequence of the same type as SEQUENCE and the given LENGTH."
 190   `(seq-dispatch ,sequence
 191      (make-list ,length)
 192      (make-vector-like ,sequence ,length)
 193      (sb!sequence:make-sequence-like ,sequence ,length)))
 194
 195 (defun bad-sequence-type-error (type-spec)
 196   (declare (optimize allow-non-returning-tail-call))
 197   (error 'simple-type-error
 198          :datum type-spec
 199          :expected-type '(satisfies is-a-valid-sequence-type-specifier-p)
 200          :format-control "~S is a bad type specifier for sequences."
 201          :format-arguments (list type-spec)))
 202
 203 (defun sequence-type-length-mismatch-error (type length)
 204   (declare (optimize allow-non-returning-tail-call))
 205   (error 'simple-type-error
 206          :datum length
 207          :expected-type (cond ((array-type-p type)
 208                                `(eql ,(car (array-type-dimensions type))))
 209                               ((type= type (specifier-type 'null))
 210                                '(eql 0))
 211                               ((cons-type-p type)
 212                                '(integer 1))
 213                               (t (bug "weird type in S-T-L-M-ERROR")))
 214          ;; FIXME: this format control causes ugly printing.  There's
 215          ;; probably some ~<~@:_~> incantation that would make it
 216          ;; nicer. -- CSR, 2002-10-18
 217          :format-control "The length requested (~S) does not match the type restriction in ~S."
 218          :format-arguments (list length (type-specifier type))))
 219
 220 (defun sequence-type-too-hairy (type-spec)
 221   ;; FIXME: Should this be a BUG? I'm inclined to think not; there are
 222   ;; words that give some but not total support to this position in
 223   ;; ANSI.  Essentially, we are justified in throwing this on
 224   ;; e.g. '(OR SIMPLE-VECTOR (VECTOR FIXNUM)), but maybe not (by ANSI)
 225   ;; on '(CONS * (CONS * NULL)) -- CSR, 2002-10-18
 226
 227   ;; On the other hand, I'm not sure it deserves to be a type-error,
 228   ;; either. -- bem, 2005-08-10
 229   (declare (optimize allow-non-returning-tail-call))
 230   (error 'simple-program-error
 231          :format-control "~S is too hairy for sequence functions."
 232          :format-arguments (list type-spec)))
 233
 234 (sb!xc:defmacro when-extended-sequence-type
 235     ((type-specifier type
 236       &key
 237       expandedp
 238       (expanded (gensym "EXPANDED"))
 239       (class (gensym "CLASS"))
 240       (prototype (gensym "PROTOTYPE") prototypep))
 241      &body body)
 242   (once-only ((type-specifier type-specifier) (type type))
 243     `(when (csubtypep ,type (specifier-type 'sequence))
 244        (binding* ((,expanded ,(if expandedp
 245                                   type-specifier
 246                                   `(typexpand ,type-specifier)))
 247                   (,class (if (typep ,expanded 'class)
 248                               ,expanded
 249                               (find-class ,expanded nil))
 250                           :exit-if-null)
 251                   (,prototype (sb!mop:class-prototype
 252                                (sb!pcl:ensure-class-finalized ,class))))
 253          ,@(unless prototypep `((ignore ,prototype)))
 254          ,@body))))
 255
 256 (defun is-a-valid-sequence-type-specifier-p (type)
 257   (let ((type (specifier-type type)))
 258     (or (csubtypep type (specifier-type 'list))
 259         (csubtypep type (specifier-type 'vector)))))
 260
 261 ;;; It's possible with some sequence operations to declare the length
 262 ;;; of a result vector, and to be safe, we really ought to verify that
 263 ;;; the actual result has the declared length.
 264 (defun vector-of-checked-length-given-length (vector declared-length)
 265   (declare (type vector vector))
 266   (declare (type index declared-length))
 267   (let ((actual-length (length vector)))
 268     (unless (= actual-length declared-length)
 269       (error 'simple-type-error
 270              :datum vector
 271              :expected-type `(vector ,declared-length)
 272              :format-control
 273              "Vector length (~W) doesn't match declared length (~W)."
 274              :format-arguments (list actual-length declared-length))))
 275   vector)
 276
 277 (defun sequence-of-checked-length-given-type (sequence result-type)
 278   (let ((ctype (specifier-type result-type)))
 279     (if (not (array-type-p ctype))
 280         sequence
 281         (let ((declared-length (first (array-type-dimensions ctype))))
 282           (if (eq declared-length '*)
 283               sequence
 284               (vector-of-checked-length-given-length sequence
 285                                                      declared-length))))))
 286
 287 (declaim (ftype (function (sequence index) nil) signal-index-too-large-error))
 288 (defun signal-index-too-large-error (sequence index)
 289   (declare (optimize allow-non-returning-tail-call))
 290   (let* ((length (length sequence))
 291          (max-index (and (plusp length)
 292                          (1- length))))
 293     (error 'index-too-large-error
 294            :datum index
 295            :expected-type (if max-index
 296                               `(integer 0 ,max-index)
 297                               ;; This seems silly, is there something better?
 298                               '(integer 0 (0))))))
 299
 300 (declaim (ftype (function (t t t) nil) sequence-bounding-indices-bad-error))
 301 (defun sequence-bounding-indices-bad-error (sequence start end)
 302   (declare (optimize allow-non-returning-tail-call))
 303   (let ((size (length sequence)))
 304     (error 'bounding-indices-bad-error
 305            :datum (cons start end)
 306            :expected-type `(cons (integer 0 ,size)
 307                                  (integer ,start ,size))
 308            :object sequence)))
 309
 310 (declaim (ftype (function (t t t) nil) array-bounding-indices-bad-error))
 311 (defun array-bounding-indices-bad-error (array start end)
 312   (declare (optimize allow-non-returning-tail-call))
 313   (let ((size (array-total-size array)))
 314     (error 'bounding-indices-bad-error
 315            :datum (cons start end)
 316            :expected-type `(cons (integer 0 ,size)
 317                                  (integer ,start ,size))
 318            :object array)))
 319
 320 (declaim (ftype (function (t) nil) circular-list-error))
 321 (defun circular-list-error (list)
 322   (declare (optimize allow-non-returning-tail-call))
 323   (error 'simple-type-error
 324          :format-control "List is circular:~%  ~S"
 325          :format-arguments (list list)
 326          :datum list
 327          :type '(and list (satisfies list-length))))
 328
 329 \f
 330
 331 (defun emptyp (sequence)
 332   "Returns T if SEQUENCE is an empty sequence and NIL
 333    otherwise. Signals an error if SEQUENCE is not a sequence."
 334   (declare (explicit-check sequence))
 335   (seq-dispatch-checking sequence
 336                 (null sequence)
 337                 (zerop (length sequence))
 338                 (sb!sequence:emptyp sequence)))
 339
 340 (defun elt (sequence index)
 341   "Return the element of SEQUENCE specified by INDEX."
 342   (declare (explicit-check sequence))
 343   (seq-dispatch-checking sequence
 344                 (do ((count index (1- count))
 345                      (list sequence (cdr list)))
 346                     ((= count 0)
 347                      (if (endp list)
 348                          (signal-index-too-large-error sequence index)
 349                          (car list)))
 350                   (declare (type index count)))
 351                 (progn
 352                   (when (>= index (length sequence))
 353                     (signal-index-too-large-error sequence index))
 354                   (aref sequence index))
 355                 (sb!sequence:elt sequence index)))
 356
 357 (defun %setelt (sequence index newval)
 358   "Store NEWVAL as the component of SEQUENCE specified by INDEX."
 359   (declare (explicit-check sequence))
 360   (seq-dispatch-checking sequence
 361                 (do ((count index (1- count))
 362                      (seq sequence))
 363                     ((= count 0) (rplaca seq newval) newval)
 364                   (declare (fixnum count))
 365                   (if (atom (cdr seq))
 366                       (signal-index-too-large-error sequence index)
 367                       (setq seq (cdr seq))))
 368                 (progn
 369                   (when (>= index (length sequence))
 370                     (signal-index-too-large-error sequence index))
 371                   (setf (aref sequence index) newval))
 372                 (setf (sb!sequence:elt sequence index) newval)))
 373
 374 (defun length (sequence)
 375   "Return an integer that is the length of SEQUENCE."
 376   (declare (explicit-check))
 377   (seq-dispatch-checking sequence
 378                 (length sequence)
 379                 (length sequence)
 380                 (sb!sequence:length sequence)))
 381
 382 (defun make-sequence (result-type length &key (initial-element nil iep))
 383   "Return a sequence of the given RESULT-TYPE and LENGTH, with
 384   elements initialized to INITIAL-ELEMENT."
 385   (declare (index length) (explicit-check))
 386   (let* ((expanded-type (typexpand result-type))
 387          (adjusted-type
 388           (typecase expanded-type
 389             (atom (cond
 390                     ((eq expanded-type 'string) '(vector character))
 391                     ((eq expanded-type 'simple-string)
 392                      '(simple-array character (*)))
 393                     (t expanded-type)))
 394             (cons (cond
 395                     ((eq (car expanded-type) 'string)
 396                      `(vector character ,@(cdr expanded-type)))
 397                     ((eq (car expanded-type) 'simple-string)
 398                      `(simple-array character ,(if (cdr expanded-type)
 399                                                    (cdr expanded-type)
 400                                                    '(*))))
 401                     (t expanded-type)))))
 402          (type (specifier-type adjusted-type))
 403          (list-type (specifier-type 'list)))
 404     (cond ((csubtypep type list-type)
 405            (cond
 406              ((type= type list-type)
 407               (make-list length :initial-element initial-element))
 408              ((eq type *empty-type*)
 409               (bad-sequence-type-error nil))
 410              ((type= type (specifier-type 'null))
 411               (if (= length 0)
 412                   'nil
 413                   (sequence-type-length-mismatch-error type length)))
 414              ((cons-type-p type)
 415               (multiple-value-bind (min exactp)
 416                   (sb!kernel::cons-type-length-info type)
 417                 (if exactp
 418                     (unless (= length min)
 419                       (sequence-type-length-mismatch-error type length))
 420                     (unless (>= length min)
 421                       (sequence-type-length-mismatch-error type length)))
 422                 (make-list length :initial-element initial-element)))
 423              ;; We'll get here for e.g. (OR NULL (CONS INTEGER *)),
 424              ;; which may seem strange and non-ideal, but then I'd say
 425              ;; it was stranger to feed that type in to MAKE-SEQUENCE.
 426              (t (sequence-type-too-hairy (type-specifier type)))))
 427           ((csubtypep type (specifier-type 'vector))
 428            (cond
 429              (;; is it immediately obvious what the result type is?
 430               (typep type 'array-type)
 431               (aver (= (length (array-type-dimensions type)) 1))
 432               (let* ((etype (type-specifier
 433                              (array-type-specialized-element-type type)))
 434                      (etype (if (eq etype '*) t etype))
 435                      (type-length (car (array-type-dimensions type))))
 436                 (unless (or (eq type-length '*)
 437                             (= type-length length))
 438                   (sequence-type-length-mismatch-error type length))
 439                 (if iep
 440                     (make-array length :element-type etype
 441                                 :initial-element initial-element)
 442                     (make-array length :element-type etype))))
 443              (t (sequence-type-too-hairy (type-specifier type)))))
 444           ((when-extended-sequence-type
 445                (expanded-type type :expandedp t :prototype prototype)
 446              ;; This function has the EXPLICIT-CHECK declaration, so
 447              ;; we manually assert that it returns a SEQUENCE.
 448              (the extended-sequence
 449                   (if iep
 450                       (sb!sequence:make-sequence-like
 451                        prototype length :initial-element initial-element)
 452                       (sb!sequence:make-sequence-like
 453                        prototype length)))))
 454           (t (bad-sequence-type-error (type-specifier type))))))
 455 \f
 456 ;;;; SUBSEQ
 457 ;;;;
 458
 459 (!define-array-dispatch vector-subseq-dispatch (array start end)
 460   (declare (optimize speed (safety 0)))
 461   (declare (type index start end))
 462   (subseq array start end))
 463
 464 ;;;; The support routines for SUBSEQ are used by compiler transforms,
 465 ;;;; so we worry about dealing with END being supplied or defaulting
 466 ;;;; to NIL at this level.
 467
 468 (defun vector-subseq* (sequence start end)
 469   (declare (type vector sequence))
 470   (declare (type index start)
 471            (type (or null index) end)
 472            (optimize speed))
 473   (with-array-data ((data sequence)
 474                     (start start)
 475                     (end end)
 476                     :check-fill-pointer t
 477                     :force-inline t)
 478     (vector-subseq-dispatch data start end)))
 479
 480 (defun list-subseq* (sequence start end)
 481   (declare (type list sequence)
 482            (type unsigned-byte start)
 483            (type (or null unsigned-byte) end))
 484   (flet ((oops ()
 485            (sequence-bounding-indices-bad-error sequence start end)))
 486     (let ((pointer sequence))
 487       (unless (zerop start)
 488         ;; If START > 0 the list cannot be empty. So CDR down to
 489         ;; it START-1 times, check that we still have something, then
 490         ;; CDR the final time.
 491         ;;
 492         ;; If START was zero, the list may be empty if END is NIL or
 493         ;; also zero.
 494         (when (> start 1)
 495           (setf pointer (nthcdr (1- start) pointer)))
 496         (if pointer
 497             (pop pointer)
 498             (oops)))
 499       (if end
 500           (let ((n (- end start)))
 501             (when (minusp n)
 502               (oops))
 503             (when (plusp n)
 504               (let* ((head (list nil))
 505                      (tail head))
 506                 (declare (dynamic-extent head))
 507                 (macrolet ((pop-one ()
 508                              `(let ((tmp (list (pop pointer))))
 509                                 (setf (cdr tail) tmp
 510                                       tail tmp))))
 511                   ;; Bignum case
 512                   (loop until (fixnump n)
 513                         do (pop-one)
 514                            (decf n))
 515                   ;; Fixnum case, but leave last element, so we should
 516                   ;; still have something left in the sequence.
 517                   (let ((m (1- n)))
 518                     (declare (fixnum m))
 519                     (loop repeat m
 520                           do (pop-one)))
 521                   (unless pointer
 522                     (oops))
 523                   ;; OK, pop the last one.
 524                   (pop-one)
 525                   (cdr head)))))
 526             (loop while pointer
 527                   collect (pop pointer))))))
 528
 529 (defun subseq (sequence start &optional end)
 530   "Return a copy of a subsequence of SEQUENCE starting with element number
 531    START and continuing to the end of SEQUENCE or the optional END."
 532   (declare (explicit-check sequence :result))
 533   (seq-dispatch-checking=>seq sequence
 534     (list-subseq* sequence start end)
 535     (vector-subseq* sequence start end)
 536     (sb!sequence:subseq sequence start end)))
 537 \f
 538 ;;;; COPY-SEQ
 539
 540 (defun copy-seq (sequence)
 541   "Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ."
 542   (declare (explicit-check sequence :result))
 543   (seq-dispatch-checking sequence
 544     (list-copy-seq* sequence)
 545     (vector-subseq* sequence 0 nil)
 546     ;; Copying an extended sequence has to return an extended-sequence
 547     ;; and not just any SEQUENCE.
 548     (the extended-sequence (values (sb!sequence:copy-seq sequence)))))
 549
 550 (defun list-copy-seq* (sequence)
 551   (!copy-list-macro sequence :check-proper-list t))
 552 \f
 553 ;;;; FILL
 554
 555 (defun list-fill* (sequence item start end)
 556   (declare (type list sequence)
 557            (type unsigned-byte start)
 558            (type (or null unsigned-byte) end))
 559   (flet ((oops ()
 560            (sequence-bounding-indices-bad-error sequence start end)))
 561     (let ((pointer sequence))
 562       (unless (zerop start)
 563         ;; If START > 0 the list cannot be empty. So CDR down to it
 564         ;; START-1 times, check that we still have something, then CDR
 565         ;; the final time.
 566         ;;
 567         ;; If START was zero, the list may be empty if END is NIL or
 568         ;; also zero.
 569         (unless (= start 1)
 570           (setf pointer (nthcdr (1- start) pointer)))
 571         (if pointer
 572             (pop pointer)
 573             (oops)))
 574       (if end
 575           (let ((n (- end start)))
 576             (declare (integer n))
 577             (when (minusp n)
 578               (oops))
 579             (when (plusp n)
 580               (loop repeat n
 581                     do (setf pointer (cdr (rplaca pointer item))))))
 582           (loop while pointer
 583                 do (setf pointer (cdr (rplaca pointer item)))))))
 584   sequence)
 585
 586 (defglobal %%fill-bashers%% (make-array (1+ sb!vm:widetag-mask)))
 587 #.`(progn
 588    ,@(loop for saetp across sb!vm:*specialized-array-element-type-properties*
 589            for et = (sb!vm:saetp-specifier saetp)
 590            if (or (null et)
 591                   (sb!vm:valid-bit-bash-saetp-p saetp))
 592            collect
 593            (multiple-value-bind (basher value-transform)
 594                (if et
 595                    (sb!c::find-basher saetp)
 596                    '(lambda (item vector start length)
 597                      (declare (ignore item start length))
 598                      (data-nil-vector-ref (truly-the (simple-array nil (*)) vector) 0)))
 599              `(setf
 600                (aref %%fill-bashers%% ,(sb!vm:saetp-typecode saetp))
 601                (cons #',basher
 602                      ,(if et
 603                           `(lambda (sb!c::item)
 604                              (declare (type ,et sb!c::item))
 605                              ,value-transform)
 606                           '#'identity))))
 607            else do
 608            ;; vector-fill* depends on this assertion
 609            (assert (member et '(t (complex double-float)
 610                                 #!-64-bit (complex single-float)
 611                                 #!-64-bit double-float)
 612                            :test #'equal))))
 613
 614 (defun vector-fill* (vector item start end)
 615   (declare (type index start) (type (or index null) end)
 616            (optimize speed))
 617   (with-array-data ((vector vector)
 618                     (start start)
 619                     (end end)
 620                     :force-inline t
 621                     :check-fill-pointer t)
 622     (if (simple-vector-p vector)
 623         (locally
 624             (declare (optimize (speed 3) (safety 0))) ; transform will kick in
 625           (fill (truly-the simple-vector vector) item
 626                 :start start :end end))
 627         (let* ((widetag (%other-pointer-widetag vector))
 628                (bashers (svref %%fill-bashers%% widetag)))
 629           (macrolet ((fill-float (type)
 630                        `(locally
 631                             (declare (optimize (speed 3) (safety 0))
 632                                      (type ,type item)
 633                                      (type (simple-array ,type (*))
 634                                            vector))
 635                           (do ((index start (1+ index)))
 636                               ((= index end))
 637                             (declare (index index))
 638                             (setf (aref vector index) item)))))
 639             (cond ((neq bashers 0)
 640                    (funcall (truly-the function (car (truly-the cons bashers)))
 641                             (funcall (truly-the function (cdr bashers)) item)
 642                             vector start (- end start)))
 643                   #!-64-bit
 644                   ((eq widetag sb!vm:simple-array-double-float-widetag)
 645                    (fill-float double-float))
 646                   #!-64-bit
 647                   ((eq widetag sb!vm:simple-array-complex-single-float-widetag)
 648                    (fill-float (complex single-float)))
 649                   (t
 650                    (fill-float (complex double-float))))))))
 651   vector)
 652
 653 (defun string-fill* (sequence item start end)
 654   (declare (string sequence))
 655   (with-array-data ((data sequence)
 656                     (start start)
 657                     (end end)
 658                     :force-inline t
 659                     :check-fill-pointer t)
 660     ;; DEFTRANSFORM for FILL will turn these into
 661     ;; calls to UB*-BASH-FILL.
 662     (etypecase data
 663       #!+sb-unicode
 664       ((simple-array character (*))
 665        (let ((item (locally (declare (optimize (safety 3)))
 666                      (the character item))))
 667          (fill data item :start start :end end)))
 668       ((simple-array base-char (*))
 669        (let ((item (locally (declare (optimize (safety 3)))
 670                      (the base-char item))))
 671          (fill data item :start start :end end))))))
 672
 673 (defun fill (sequence item &key (start 0) end)
 674   "Replace the specified elements of SEQUENCE with ITEM."
 675   (declare (explicit-check sequence :result))
 676   (seq-dispatch-checking=>seq sequence
 677    (list-fill* sequence item start end)
 678    (vector-fill* sequence item start end)
 679    (sb!sequence:fill sequence item
 680                      :start start
 681                      :end (%check-generic-sequence-bounds sequence start end))))
 682 \f
 683 ;;;; REPLACE
 684
 685 (eval-when (:compile-toplevel :execute)
 686
 687 ;;; If we are copying around in the same vector, be careful not to copy the
 688 ;;; same elements over repeatedly. We do this by copying backwards.
 689 (sb!xc:defmacro mumble-replace-from-mumble ()
 690   `(if (and (eq target-sequence source-sequence) (> target-start source-start))
 691        (let ((nelts (min (- target-end target-start)
 692                          (- source-end source-start))))
 693          (do ((target-index (+ (the fixnum target-start) (the fixnum nelts) -1)
 694                             (1- target-index))
 695               (source-index (+ (the fixnum source-start) (the fixnum nelts) -1)
 696                             (1- source-index)))
 697              ((= target-index (the fixnum (1- target-start))) target-sequence)
 698            (declare (fixnum target-index source-index))
 699            ;; disable bounds checking
 700            (declare (optimize (safety 0)))
 701            (setf (aref target-sequence target-index)
 702                  (aref source-sequence source-index))))
 703        (do ((target-index target-start (1+ target-index))
 704             (source-index source-start (1+ source-index)))
 705            ((or (= target-index (the fixnum target-end))
 706                 (= source-index (the fixnum source-end)))
 707             target-sequence)
 708          (declare (fixnum target-index source-index))
 709          ;; disable bounds checking
 710          (declare (optimize (safety 0)))
 711          (setf (aref target-sequence target-index)
 712                (aref source-sequence source-index)))))
 713
 714 (sb!xc:defmacro list-replace-from-list ()
 715   `(if (and (eq target-sequence source-sequence) (> target-start source-start))
 716        (let ((new-elts (subseq source-sequence source-start
 717                                (+ (the fixnum source-start)
 718                                   (the fixnum
 719                                        (min (- (the fixnum target-end)
 720                                                (the fixnum target-start))
 721                                             (- (the fixnum source-end)
 722                                                (the fixnum source-start))))))))
 723          (do ((n new-elts (cdr n))
 724               (o (nthcdr target-start target-sequence) (cdr o)))
 725              ((null n) target-sequence)
 726            (rplaca o (car n))))
 727        (do ((target-index target-start (1+ target-index))
 728             (source-index source-start (1+ source-index))
 729             (target-sequence-ref (nthcdr target-start target-sequence)
 730                                  (cdr target-sequence-ref))
 731             (source-sequence-ref (nthcdr source-start source-sequence)
 732                                  (cdr source-sequence-ref)))
 733            ((or (= target-index (the fixnum target-end))
 734                 (= source-index (the fixnum source-end))
 735                 (null target-sequence-ref) (null source-sequence-ref))
 736             target-sequence)
 737          (declare (fixnum target-index source-index))
 738          (rplaca target-sequence-ref (car source-sequence-ref)))))
 739
 740 (sb!xc:defmacro list-replace-from-mumble ()
 741   `(do ((target-index target-start (1+ target-index))
 742         (source-index source-start (1+ source-index))
 743         (target-sequence-ref (nthcdr target-start target-sequence)
 744                              (cdr target-sequence-ref)))
 745        ((or (= target-index (the fixnum target-end))
 746             (= source-index (the fixnum source-end))
 747             (null target-sequence-ref))
 748         target-sequence)
 749      (declare (fixnum source-index target-index))
 750      (rplaca target-sequence-ref (aref source-sequence source-index))))
 751
 752 (sb!xc:defmacro mumble-replace-from-list ()
 753   `(do ((target-index target-start (1+ target-index))
 754         (source-index source-start (1+ source-index))
 755         (source-sequence (nthcdr source-start source-sequence)
 756                          (cdr source-sequence)))
 757        ((or (= target-index (the fixnum target-end))
 758             (= source-index (the fixnum source-end))
 759             (null source-sequence))
 760         target-sequence)
 761      (declare (fixnum target-index source-index))
 762      (setf (aref target-sequence target-index) (car source-sequence))))
 763
 764 ) ; EVAL-WHEN
 765
 766 ;;;; The support routines for REPLACE are used by compiler transforms, so we
 767 ;;;; worry about dealing with END being supplied or defaulting to NIL
 768 ;;;; at this level.
 769
 770 (defun list-replace-from-list* (target-sequence source-sequence target-start
 771                                 target-end source-start source-end)
 772   (when (null target-end) (setq target-end (length target-sequence)))
 773   (when (null source-end) (setq source-end (length source-sequence)))
 774   (list-replace-from-list))
 775
 776 (defun list-replace-from-vector* (target-sequence source-sequence target-start
 777                                   target-end source-start source-end)
 778   (when (null target-end) (setq target-end (length target-sequence)))
 779   (when (null source-end) (setq source-end (length source-sequence)))
 780   (list-replace-from-mumble))
 781
 782 (defun vector-replace-from-list* (target-sequence source-sequence target-start
 783                                   target-end source-start source-end)
 784   (when (null target-end) (setq target-end (length target-sequence)))
 785   (when (null source-end) (setq source-end (length source-sequence)))
 786   (mumble-replace-from-list))
 787
 788 (defun vector-replace-from-vector* (target-sequence source-sequence
 789                                     target-start target-end source-start
 790                                     source-end)
 791   (when (null target-end) (setq target-end (length target-sequence)))
 792   (when (null source-end) (setq source-end (length source-sequence)))
 793   (mumble-replace-from-mumble))
 794
 795 #!+sb-unicode
 796 (defun simple-character-string-replace-from-simple-character-string*
 797     (target-sequence source-sequence
 798      target-start target-end source-start source-end)
 799   (declare (type (simple-array character (*)) target-sequence source-sequence))
 800   (when (null target-end) (setq target-end (length target-sequence)))
 801   (when (null source-end) (setq source-end (length source-sequence)))
 802   (mumble-replace-from-mumble))
 803
 804 (define-sequence-traverser replace
 805     (sequence1 sequence2 &rest args &key start1 end1 start2 end2)
 806   "Destructively modifies SEQUENCE1 by copying successive elements
 807 into it from the SEQUENCE2.
 808
 809 Elements are copied to the subseqeuence bounded by START1 and END1,
 810 from the subsequence bounded by START2 and END2. If these subsequences
 811 are not of the same length, then the shorter length determines how
 812 many elements are copied."
 813   (declare (truly-dynamic-extent args))
 814   (declare (explicit-check sequence1 sequence2 :result))
 815   (let* (;; KLUDGE: absent either rewriting FOO-REPLACE-FROM-BAR, or
 816          ;; excessively polluting DEFINE-SEQUENCE-TRAVERSER, we rebind
 817          ;; these things here so that legacy code gets the names it's
 818          ;; expecting.  We could use &AUX instead :-/.
 819          (target-sequence sequence1)
 820          (source-sequence sequence2)
 821          (target-start start1)
 822          (source-start start2)
 823          (target-end (or end1 length1))
 824          (source-end (or end2 length2)))
 825     (seq-dispatch-checking target-sequence
 826       (seq-dispatch-checking source-sequence
 827         (return-from replace (list-replace-from-list))
 828         (return-from replace (list-replace-from-mumble))
 829         nil)
 830       (seq-dispatch-checking source-sequence
 831         (return-from replace (mumble-replace-from-list))
 832         (return-from replace (mumble-replace-from-mumble))
 833         nil)
 834       t)
 835     ;; If sequence1 is an extended-sequence, we know nothing about sequence2.
 836     ;; If sequence1 was a list or vector, then sequence2 is an extended-sequence
 837     ;; or not a sequence. Either way, check it.
 838     (the sequence
 839       (values (apply #'sb!sequence:replace sequence1
 840                      (the sequence sequence2) args)))))
 841 \f
 842 ;;;; REVERSE
 843 (defun reverse (sequence)
 844   "Return a new sequence containing the same elements but in reverse order."
 845   (declare (explicit-check))
 846   (seq-dispatch-checking sequence
 847     (list-reverse sequence)
 848     (vector-reverse sequence)
 849     ;; The type deriver says that LIST => LIST and VECTOR => VECTOR
 850     ;; but does not claim to know anything about extended-sequences.
 851     ;; So this could theoretically return any subtype of SEQUENCE
 852     ;; given an EXTENDED-SEQUENCE as input. But fndb says this returns
 853     ;; a CONSED-SEQUENCE, which precludes non-simple vectors.
 854     ;; But a CLOS sequence can apparently decide to return a LIST when
 855     ;; reversed. [Is that too weird? Make this EXTENDED-SEQUENCE maybe?]
 856     (the consed-sequence (values (sb!sequence:reverse sequence)))))
 857
 858 (defun list-reverse (list)
 859   (do ((new-list ()))
 860       ((endp list) new-list)
 861     (push (pop list) new-list)))
 862
 863 (defmacro word-specialized-vector-tag-p (tag)
 864   `(or
 865     ,@(loop for saetp across sb!vm:*specialized-array-element-type-properties*
 866            when (and (eq (sb!vm:saetp-n-bits saetp) sb!vm:n-word-bits)
 867                      (not (eq (sb!vm:saetp-specifier saetp) t)))
 868            collect `(eq ,tag ,(sb!vm:saetp-typecode saetp)))))
 869
 870 (defun reverse-word-specialized-vector (from to end)
 871   (declare (vector from))
 872   (do ((length (length to))
 873        (left-index 0 (1+ left-index))
 874        (right-index end))
 875       ((= left-index length))
 876     (declare (type index left-index right-index))
 877     (decf right-index)
 878     (setf (%vector-raw-bits to left-index)
 879           (%vector-raw-bits from right-index)))
 880   to)
 881
 882 (defun vector-reverse (vector)
 883   (declare (vector vector))
 884   (let ((length (length vector)))
 885     (with-array-data ((vector vector) (start) (end)
 886                       :check-fill-pointer t)
 887       (declare (ignore start))
 888       (let* ((tag (%other-pointer-widetag vector))
 889              (new-vector (allocate-vector-with-widetag tag length nil)))
 890         (cond ((= tag sb!vm:simple-vector-widetag)
 891                (do ((left-index 0 (1+ left-index))
 892                     (right-index end))
 893                    ((= left-index length))
 894                  (declare (type index left-index right-index))
 895                  (decf right-index)
 896                  (setf (svref new-vector left-index)
 897                        (svref vector right-index))))
 898               ((word-specialized-vector-tag-p tag)
 899                (reverse-word-specialized-vector vector new-vector end))
 900               (t
 901                (let ((getter (the function (svref %%data-vector-reffers%% tag)))
 902                      (setter (the function (svref %%data-vector-setters%% tag))))
 903                  (declare (fixnum length))
 904                  (do ((forward-index 0 (1+ forward-index))
 905                       (backward-index (1- end) (1- backward-index)))
 906                      ((= forward-index length))
 907                    (declare (fixnum forward-index backward-index))
 908                    (funcall setter new-vector forward-index
 909                             (funcall getter vector backward-index))))))
 910         new-vector))))
 911 \f
 912 ;;;; NREVERSE
 913
 914 (defun list-nreverse (list)
 915   (do ((1st (cdr list) (if (endp 1st) 1st (cdr 1st)))
 916        (2nd list 1st)
 917        (3rd '() 2nd))
 918       ((atom 2nd) 3rd)
 919     (rplacd 2nd 3rd)))
 920
 921 (defun nreverse-word-specialized-vector (vector start end)
 922   (do ((left-index start (1+ left-index))
 923        (right-index (1- end) (1- right-index)))
 924       ((<= right-index left-index))
 925     (declare (type index left-index right-index))
 926     (let ((left (%vector-raw-bits vector left-index))
 927           (right (%vector-raw-bits vector right-index)))
 928       (setf (%vector-raw-bits vector left-index) right
 929             (%vector-raw-bits vector right-index) left)))
 930   vector)
 931
 932 (defun vector-nreverse (vector)
 933   (declare (vector vector))
 934   (when (> (length vector) 1)
 935     (with-array-data ((vector vector) (start) (end)
 936                       :check-fill-pointer t)
 937       (let ((tag (%other-pointer-widetag vector)))
 938         (cond ((= tag sb!vm:simple-vector-widetag)
 939                (do ((left-index start (1+ left-index))
 940                     (right-index (1- end) (1- right-index)))
 941                    ((<= right-index left-index))
 942                  (declare (type index left-index right-index))
 943                  (let ((left (svref vector left-index))
 944                        (right (svref vector right-index)))
 945                    (setf (svref vector left-index) right
 946                          (svref vector right-index) left))))
 947               ((word-specialized-vector-tag-p tag)
 948                (nreverse-word-specialized-vector vector start end))
 949               (t
 950                (let* ((getter (the function (svref %%data-vector-reffers%% tag)))
 951                       (setter (the function (svref %%data-vector-setters%% tag))))
 952                  (do ((left-index start (1+ left-index))
 953                       (right-index (1- end) (1- right-index)))
 954                      ((<= right-index left-index))
 955                    (declare (type index left-index right-index))
 956                    (let ((left (funcall getter vector left-index))
 957                          (right (funcall getter vector right-index)))
 958                      (funcall setter vector left-index right)
 959                      (funcall setter vector right-index left)))))))))
 960   vector)
 961
 962 (defun nreverse (sequence)
 963   "Return a sequence of the same elements in reverse order; the argument
 964    is destroyed."
 965   (declare (explicit-check))
 966   (seq-dispatch-checking sequence
 967     (list-nreverse sequence)
 968     (vector-nreverse sequence)
 969     ;; The type deriver for this is 'result-type-first-arg',
 970     ;; meaning it should return definitely an EXTENDED-SEQUENCE
 971     ;; and not a list or vector.
 972     (the extended-sequence (values (sb!sequence:nreverse sequence)))))
 973 \f
 974
 975 (defmacro sb!sequence:dosequence ((element sequence &optional return) &body body)
 976   "Executes BODY with ELEMENT subsequently bound to each element of
 977   SEQUENCE, then returns RETURN."
 978   (multiple-value-bind (forms decls) (parse-body body nil)
 979     (once-only ((sequence sequence))
 980       (with-unique-names (state limit from-end step endp elt)
 981         `(block nil
 982            (seq-dispatch ,sequence
 983              (dolist (,element ,sequence ,return) ,@body)
 984              (do-vector-data (,element ,sequence ,return) ,@body)
 985              (multiple-value-bind (,state ,limit ,from-end ,step ,endp ,elt)
 986                  (sb!sequence:make-sequence-iterator ,sequence)
 987                (declare (function ,step ,endp ,elt))
 988                (do ((,state ,state (funcall ,step ,sequence ,state ,from-end)))
 989                    ((funcall ,endp ,sequence ,state ,limit ,from-end)
 990                     (let ((,element nil))
 991                       ,@(filter-dolist-declarations decls)
 992                       (declare (ignorable ,element))
 993                       ,return))
 994                  (let ((,element (funcall ,elt ,sequence ,state)))
 995                    ,@decls
 996                    (tagbody
 997                       ,@forms))))))))))
 998
 999 \f
1000 ;;;; CONCATENATE
1001
1002 (defun concatenate (result-type &rest sequences)
1003   "Return a new sequence of all the argument sequences concatenated together
1004   which shares no structure with the original argument sequences of the
1005   specified RESULT-TYPE."
1006   (declare (explicit-check)
1007            (dynamic-extent sequences))
1008   (flet ((concat-to-simple* (type-spec sequences)
1009            (do ((seqs sequences (cdr seqs))
1010                 (total-length 0)
1011                 (lengths ()))
1012                ((null seqs)
1013                 (do ((sequences sequences (cdr sequences))
1014                      (lengths lengths (cdr lengths))
1015                      (index 0)
1016                      (result (make-sequence type-spec total-length)))
1017                     ((= index total-length) result)
1018                   (declare (fixnum index))
1019                   (let ((sequence (car sequences)))
1020                     (sb!sequence:dosequence (e sequence)
1021                       (setf (aref result index) e)
1022                       (incf index)))))
1023              (let ((length (length (car seqs))))
1024                (declare (fixnum length))
1025                (setq lengths (nconc lengths (list length)))
1026                (setq total-length (+ total-length length))))))
1027     (case result-type
1028       ;; Pick up some common cases first
1029       (list
1030        (apply #'%concatenate-to-list sequences))
1031       ((vector simple-vector)
1032        (apply #'%concatenate-to-simple-vector sequences))
1033       #!+sb-unicode
1034       ((string simple-string)
1035        (apply #'%concatenate-to-string sequences))
1036       ((simple-base-string #!-sb-unicode string #!-sb-unicode simple-string)
1037        (apply #'%concatenate-to-base-string sequences))
1038       (t
1039        (let ((type (specifier-type result-type)))
1040          (cond
1041            ((csubtypep type (specifier-type 'list))
1042             (cond
1043               ((type= type (specifier-type 'list))
1044                (apply #'%concatenate-to-list sequences))
1045               ((eq type *empty-type*)
1046                (bad-sequence-type-error nil))
1047               ((type= type (specifier-type 'null))
1048                (unless (every #'emptyp sequences)
1049                  (sequence-type-length-mismatch-error
1050                   type (reduce #'+ sequences :key #'length))) ; FIXME: circular list issues.
1051                '())
1052               ((cons-type-p type)
1053                (multiple-value-bind (min exactp)
1054                    (sb!kernel::cons-type-length-info type)
1055                  (let ((length (reduce #'+ sequences :key #'length)))
1056                    (if exactp
1057                        (unless (= length min)
1058                          (sequence-type-length-mismatch-error type length))
1059                        (unless (>= length min)
1060                          (sequence-type-length-mismatch-error type length)))
1061                    (apply #'%concatenate-to-list sequences))))
1062               (t (sequence-type-too-hairy (type-specifier type)))))
1063            ((csubtypep type (specifier-type 'vector))
1064             (concat-to-simple* result-type sequences))
1065            ((when-extended-sequence-type
1066                 (result-type type :expandedp nil :prototype prototype)
1067               ;; This function has the EXPLICIT-CHECK declaration,
1068               ;; so we manually assert that it returns a SEQUENCE.
1069               (the extended-sequence
1070                    (apply #'sb!sequence:concatenate prototype sequences))))
1071            (t
1072             (bad-sequence-type-error result-type))))))))
1073
1074 ;;; Efficient out-of-line concatenate for strings. Compiler transforms
1075 ;;; CONCATENATE 'STRING &co into these.
1076 (macrolet ((def (name element-type &rest dispatch)
1077              `(defun ,name (&rest sequences)
1078                 (declare (explicit-check)
1079                          (optimize (sb!c::insert-array-bounds-checks 0)))
1080                 (let ((length 0))
1081                   (declare (index length))
1082                   (do-rest-arg ((seq) sequences)
1083                     (incf length (length seq)))
1084                   (let ((result (make-array length :element-type ',element-type))
1085                         (start 0))
1086                     (declare (index start))
1087                     (do-rest-arg ((seq) sequences)
1088                       (string-dispatch (,@dispatch t)
1089                                        seq
1090                         (let ((length (length seq)))
1091                           (replace result seq :start1 start)
1092                           (incf start length))))
1093                     result)))))
1094   #!+sb-unicode
1095   (def %concatenate-to-string character
1096     (simple-array character (*)) (simple-array base-char (*)))
1097   (def %concatenate-to-base-string base-char
1098     (simple-array base-char (*)) #!+sb-unicode (simple-array character (*)))
1099   (def %concatenate-to-simple-vector t simple-vector))
1100
1101 (defun %concatenate-to-list (&rest sequences)
1102   (declare (explicit-check))
1103   (let* ((result (list nil))
1104          (splice result))
1105     (do-rest-arg ((sequence) sequences)
1106       (sb!sequence:dosequence (e sequence)
1107         (setf splice (cdr (rplacd splice (list e))))))
1108     (cdr result)))
1109
1110 (defun %concatenate-to-vector (widetag &rest sequences)
1111   (declare (explicit-check))
1112   (let ((length 0))
1113     (declare (index length))
1114     (do-rest-arg ((seq) sequences)
1115       (incf length (length seq)))
1116     (let ((result (allocate-vector-with-widetag widetag length nil))
1117           (setter (the function (svref %%data-vector-setters%% widetag)))
1118           (index 0))
1119       (declare (index index))
1120       (do-rest-arg ((seq) sequences)
1121         (sb!sequence:dosequence (e seq)
1122           (funcall setter result index e)
1123           (incf index)))
1124       result)))
1125 \f
1126 ;;;; MAP
1127
1128 ;;; helper functions to handle arity-1 subcases of MAP
1129 (defun %map-to-list-arity-1 (fun sequence)
1130   (declare (explicit-check))
1131   (let ((reversed-result nil)
1132         (really-fun (%coerce-callable-to-fun fun)))
1133     (sb!sequence:dosequence (element sequence)
1134       (push (funcall really-fun element)
1135             reversed-result))
1136     (nreverse reversed-result)))
1137 (defun %map-to-simple-vector-arity-1 (fun sequence)
1138   (declare (explicit-check))
1139   (let ((result (make-array (length sequence)))
1140         (index 0)
1141         (really-fun (%coerce-callable-to-fun fun)))
1142     (declare (type index index))
1143     (sb!sequence:dosequence (element sequence)
1144       (setf (aref result index)
1145             (funcall really-fun element))
1146       (incf index))
1147     result))
1148 (defun %map-for-effect-arity-1 (fun sequence)
1149   (declare (explicit-check))
1150   (let ((really-fun (%coerce-callable-to-fun fun)))
1151     (sb!sequence:dosequence (element sequence)
1152       (funcall really-fun element)))
1153   nil)
1154
1155 (declaim (maybe-inline %map-for-effect))
1156 (defun %map-for-effect (fun sequences)
1157   (declare (type function fun) (type list sequences))
1158   (let ((%sequences sequences)
1159         (%iters (mapcar (lambda (s)
1160                           (seq-dispatch s
1161                             s
1162                             0
1163                             (multiple-value-list
1164                              (sb!sequence:make-sequence-iterator s))))
1165                         sequences))
1166         (%apply-args (make-list (length sequences))))
1167     ;; this is almost efficient (except in the general case where we
1168     ;; trampoline to MAKE-SEQUENCE-ITERATOR; if we had DX allocation
1169     ;; of MAKE-LIST, the whole of %MAP would be cons-free.
1170     ;; TODO: on x86-64, we do have. Now see if the above remark is true.
1171     (declare (type list %sequences %iters %apply-args))
1172     (loop
1173      (do ((in-sequences  %sequences  (cdr in-sequences))
1174           (in-iters      %iters      (cdr in-iters))
1175           (in-apply-args %apply-args (cdr in-apply-args)))
1176          ((null in-sequences) (apply fun %apply-args))
1177        (let ((i (car in-iters)))
1178          (declare (type (or list index) i))
1179          (cond
1180            ((listp (car in-sequences))
1181             (if (null i)
1182                 (return-from %map-for-effect nil)
1183                 (setf (car in-apply-args) (car i)
1184                       (car in-iters) (cdr i))))
1185            ((typep i 'index)
1186             (let ((v (the vector (car in-sequences))))
1187               (if (>= i (length v))
1188                   (return-from %map-for-effect nil)
1189                   (setf (car in-apply-args) (aref v i)
1190                         (car in-iters) (1+ i)))))
1191            (t
1192             ;; While on one hand this could benefit from a zero-safety ds-bind,
1193             ;; on the other, why not coerce these tuples to vectors or structs?
1194             (destructuring-bind (state limit from-end step endp elt &rest ignore)
1195                 i
1196               (declare (type function step endp elt)
1197                        (ignore ignore))
1198               (let ((s (car in-sequences)))
1199                 (if (funcall endp s state limit from-end)
1200                     (return-from %map-for-effect nil)
1201                     (progn
1202                       (setf (car in-apply-args) (funcall elt s state))
1203                       (setf (caar in-iters) (funcall step s state from-end)))))))))))))
1204 (defun %map-to-list (fun sequences)
1205   (declare (type function fun)
1206            (type list sequences))
1207   (let ((result nil))
1208     (flet ((f (&rest args)
1209              (declare (truly-dynamic-extent args))
1210              (push (apply fun args) result)))
1211       (declare (truly-dynamic-extent #'f))
1212       (%map-for-effect #'f sequences))
1213     (nreverse result)))
1214 (defun %map-to-vector (output-type-spec fun sequences)
1215   (declare (type function fun)
1216            (type list sequences))
1217   (let ((min-len 0))
1218     (flet ((f (&rest args)
1219              (declare (truly-dynamic-extent args))
1220              (declare (ignore args))
1221              (incf min-len)))
1222       (declare (truly-dynamic-extent #'f))
1223       (%map-for-effect #'f sequences))
1224     (let ((result (make-sequence output-type-spec min-len))
1225           (i 0))
1226       (declare (type (simple-array * (*)) result))
1227       (flet ((f (&rest args)
1228                (declare (truly-dynamic-extent args))
1229                (setf (aref result i) (apply fun args))
1230                (incf i)))
1231         (declare (truly-dynamic-extent #'f))
1232         (%map-for-effect #'f sequences))
1233       result)))
1234
1235 ;;; %MAP is just MAP without the final just-to-be-sure check that
1236 ;;; length of the output sequence matches any length specified
1237 ;;; in RESULT-TYPE.
1238 (defun %map (result-type function &rest sequences)
1239   (declare (explicit-check))
1240   (declare (dynamic-extent sequences))
1241   ;; Everything that we end up calling uses %COERCE-TO-CALLABLE
1242   ;; on FUNCTION so we don't need to declare it of type CALLABLE here.
1243   ;; Additionally all the arity-1 mappers use SEQ-DISPATCH which asserts
1244   ;; that the input is a SEQUENCE. Despite SEQ-DISPATCH being "less safe"
1245   ;; than SEQ-DISPATCH-CHECKING, both are in fact equally safe, because
1246   ;; the ARRAY case (which assumes that all arrays are vectors) utilizes
1247   ;; %WITH-ARRAY-DATA/FP which asserts that its input is a vector.
1248   (labels ((slower-map (type)
1249              (let ((really-fun (%coerce-callable-to-fun function)))
1250                (cond
1251                  ((eq type *empty-type*)
1252                   (%map-for-effect really-fun sequences))
1253                  ((csubtypep type (specifier-type 'list))
1254                   (%map-to-list really-fun sequences))
1255                  ((csubtypep type (specifier-type 'vector))
1256                   (%map-to-vector result-type really-fun sequences))
1257                  ((when-extended-sequence-type
1258                       (result-type type :expandedp nil :prototype prototype)
1259                     ;; This function has the EXPLICIT-CHECK
1260                     ;; declaration, so we manually assert that it
1261                     ;; returns a SEQUENCE.
1262                     (the extended-sequence
1263                          (apply #'sb!sequence:map
1264                                 prototype really-fun sequences))))
1265                  (t
1266                   (bad-sequence-type-error result-type))))))
1267     ;; Handle some easy cases faster
1268     (if (/= (length sequences) 1)
1269         (slower-map (specifier-type result-type))
1270         (let ((first-sequence (fast-&rest-nth 0 sequences)))
1271           (case result-type
1272            ((nil)
1273             (%map-for-effect-arity-1 function first-sequence))
1274            ((list cons)
1275             (%map-to-list-arity-1 function first-sequence))
1276            ((vector simple-vector)
1277             (%map-to-simple-vector-arity-1 function first-sequence))
1278            (t
1279             (let ((type (specifier-type result-type)))
1280               (cond ((eq type *empty-type*)
1281                      (%map-for-effect-arity-1 function first-sequence))
1282                     ((csubtypep type (specifier-type 'list))
1283                      (%map-to-list-arity-1 function first-sequence))
1284                     ((csubtypep type (specifier-type '(vector t)))
1285                      (%map-to-simple-vector-arity-1 function first-sequence))
1286                     (t
1287                      (slower-map type))))))))))
1288
1289 (defun map (result-type function first-sequence &rest more-sequences)
1290   (declare (explicit-check))
1291   (let ((result
1292          (apply #'%map result-type function first-sequence more-sequences)))
1293     (if (or (eq result-type 'nil) (typep result result-type))
1294         result
1295         (error 'simple-type-error
1296                :format-control "MAP result ~S is not a sequence of type ~S"
1297                :datum result
1298                :expected-type result-type
1299                :format-arguments (list result result-type)))))
1300
1301 ;;;; MAP-INTO
1302
1303 (defmacro map-into-lambda (sequences params &body body)
1304   (check-type sequences symbol)
1305   `(flet ((f ,params ,@body))
1306      (declare (truly-dynamic-extent #'f))
1307      ;; Note (MAP-INTO SEQ (LAMBDA () ...)) is a different animal,
1308      ;; hence the awkward flip between MAP and LOOP.
1309      (if ,sequences
1310          (apply #'%map nil #'f ,sequences)
1311          (loop (f)))))
1312
1313 (!define-array-dispatch vector-map-into (data start end fun sequences)
1314   (declare (type index start end)
1315            (type function fun)
1316            (type list sequences))
1317   (declare (explicit-check))
1318   (let ((index start))
1319     (declare (type index index))
1320     (block mapping
1321       (map-into-lambda sequences (&rest args)
1322         (declare (truly-dynamic-extent args))
1323         (when (eql index end)
1324           (return-from mapping))
1325         (setf (aref data index) (apply fun args))
1326         (incf index)))
1327     index))
1328
1329 ;;; Uses the machinery of (MAP NIL ...). For non-vectors we avoid
1330 ;;; computing the length of the result sequence since we can detect
1331 ;;; the end during mapping (if MAP even gets that far).
1332 ;;;
1333 ;;; For each result type, define a mapping function which is
1334 ;;; responsible for replacing RESULT-SEQUENCE elements and for
1335 ;;; terminating itself if the end of RESULT-SEQUENCE is reached.
1336 ;;; The mapping function is defined with MAP-INTO-LAMBDA.
1337 ;;;
1338 ;;; MAP-INTO-LAMBDAs are optimized since they are the inner loops.
1339 ;;; Because we are manually doing bounds checking with known types,
1340 ;;; safety is turned off for vectors and lists but kept for generic
1341 ;;; sequences.
1342 (defun map-into (result-sequence function &rest sequences)
1343   (declare (optimize (sb!c::check-tag-existence 0)))
1344   (let ((really-fun (%coerce-callable-to-fun function)))
1345     (etypecase result-sequence
1346       (vector
1347        (with-array-data ((data result-sequence) (start) (end)
1348                          ;; MAP-INTO ignores fill pointer when mapping
1349                          :check-fill-pointer nil)
1350          (let ((new-end (vector-map-into data start end really-fun sequences)))
1351            (when (array-has-fill-pointer-p result-sequence)
1352              (setf (fill-pointer result-sequence) (- new-end start))))))
1353       (list
1354        (let ((node result-sequence))
1355          (declare (type list node))
1356          (map-into-lambda sequences (&rest args)
1357            (declare (truly-dynamic-extent args))
1358            (cond ((null node)
1359                   (return-from map-into result-sequence))
1360                  ((not (listp (cdr node)))
1361                   (error 'simple-type-error
1362                          :format-control "~a is not a proper list"
1363                          :format-arguments (list result-sequence)
1364                          :expected-type 'list
1365                          :datum result-sequence)))
1366            (setf (car node) (apply really-fun args))
1367            (setf node (cdr node)))))
1368       (sequence
1369        (multiple-value-bind (iter limit from-end)
1370            (sb!sequence:make-sequence-iterator result-sequence)
1371          (map-into-lambda sequences (&rest args)
1372            (declare (truly-dynamic-extent args) (optimize speed))
1373            (when (sb!sequence:iterator-endp result-sequence
1374                                             iter limit from-end)
1375              (return-from map-into result-sequence))
1376            (setf (sb!sequence:iterator-element result-sequence iter)
1377                  (apply really-fun args))
1378            (setf iter (sb!sequence:iterator-step result-sequence
1379                                                            iter from-end)))))))
1380   result-sequence)
1381 \f
1382 ;;;; REDUCE
1383
1384 (eval-when (:compile-toplevel :execute)
1385
1386 (sb!xc:defmacro mumble-reduce (function
1387                                sequence
1388                                key
1389                                start
1390                                end
1391                                initial-value
1392                                ref)
1393   `(do ((index ,start (1+ index))
1394         (value ,initial-value))
1395        ((>= index ,end) value)
1396      (setq value (funcall ,function value
1397                           (apply-key ,key (,ref ,sequence index))))))
1398
1399 (sb!xc:defmacro mumble-reduce-from-end (function
1400                                         sequence
1401                                         key
1402                                         start
1403                                         end
1404                                         initial-value
1405                                         ref)
1406   `(do ((index (1- ,end) (1- index))
1407         (value ,initial-value)
1408         (terminus (1- ,start)))
1409        ((<= index terminus) value)
1410      (setq value (funcall ,function
1411                           (apply-key ,key (,ref ,sequence index))
1412                           value))))
1413
1414 (sb!xc:defmacro list-reduce (function
1415                              sequence
1416                              key
1417                              start
1418                              end
1419                              initial-value
1420                              ivp)
1421   `(let ((sequence (nthcdr ,start ,sequence)))
1422      (do ((count (if ,ivp ,start (1+ ,start))
1423                  (1+ count))
1424           (sequence (if ,ivp sequence (cdr sequence))
1425                     (cdr sequence))
1426           (value (if ,ivp ,initial-value (apply-key ,key (car sequence)))
1427                  (funcall ,function value (apply-key ,key (car sequence)))))
1428          ((>= count ,end) value))))
1429
1430 (sb!xc:defmacro list-reduce-from-end (function
1431                                       sequence
1432                                       key
1433                                       start
1434                                       end
1435                                       initial-value
1436                                       ivp)
1437   `(let ((sequence (nthcdr (- (length ,sequence) ,end)
1438                            (reverse ,sequence))))
1439      (do ((count (if ,ivp ,start (1+ ,start))
1440                  (1+ count))
1441           (sequence (if ,ivp sequence (cdr sequence))
1442                     (cdr sequence))
1443           (value (if ,ivp ,initial-value (apply-key ,key (car sequence)))
1444                  (funcall ,function (apply-key ,key (car sequence)) value)))
1445          ((>= count ,end) value))))
1446
1447 ) ; EVAL-WHEN
1448
1449 (define-sequence-traverser reduce (function sequence &rest args &key key
1450                                    from-end start end (initial-value nil ivp))
1451   (declare (type index start)
1452            (truly-dynamic-extent args))
1453   (declare (explicit-check sequence))
1454   (seq-dispatch-checking sequence
1455     (let ((end (or end length)))
1456       (declare (type index end))
1457       (if (= end start)
1458           (if ivp initial-value (funcall function))
1459           (if from-end
1460               (list-reduce-from-end function sequence key start end
1461                                     initial-value ivp)
1462               (list-reduce function sequence key start end
1463                            initial-value ivp))))
1464     (let ((end (or end length)))
1465       (declare (type index end))
1466       (if (= end start)
1467           (if ivp initial-value (funcall function))
1468           (if from-end
1469               (progn
1470                 (when (not ivp)
1471                   (setq end (1- (the fixnum end)))
1472                   (setq initial-value (apply-key key (aref sequence end))))
1473                 (mumble-reduce-from-end function sequence key start end
1474                                         initial-value aref))
1475               (progn
1476                 (when (not ivp)
1477                   (setq initial-value (apply-key key (aref sequence start)))
1478                   (setq start (1+ start)))
1479                 (mumble-reduce function sequence key start end
1480                                initial-value aref)))))
1481     (apply #'sb!sequence:reduce function sequence args)))
1482 \f
1483 ;;;; DELETE
1484
1485 (eval-when (:compile-toplevel :execute)
1486
1487 (sb!xc:defmacro mumble-delete (pred)
1488   `(do ((index start (1+ index))
1489         (jndex start)
1490         (number-zapped 0))
1491        ((or (= index (the fixnum end)) (= number-zapped count))
1492         (do ((index index (1+ index))           ; Copy the rest of the vector.
1493              (jndex jndex (1+ jndex)))
1494             ((= index (the fixnum length))
1495              (shrink-vector sequence jndex))
1496           (declare (fixnum index jndex))
1497           (setf (aref sequence jndex) (aref sequence index))))
1498      (declare (fixnum index jndex number-zapped))
1499      (setf (aref sequence jndex) (aref sequence index))
1500      (if ,pred
1501          (incf number-zapped)
1502          (incf jndex))))
1503
1504 (sb!xc:defmacro mumble-delete-from-end (pred)
1505   `(do ((index (1- (the fixnum end)) (1- index)) ; Find the losers.
1506         (number-zapped 0)
1507         (losers ())
1508         this-element
1509         (terminus (1- start)))
1510        ((or (= index terminus) (= number-zapped count))
1511         (do ((losers losers)                     ; Delete the losers.
1512              (index start (1+ index))
1513              (jndex start))
1514             ((or (null losers) (= index (the fixnum end)))
1515              (do ((index index (1+ index))       ; Copy the rest of the vector.
1516                   (jndex jndex (1+ jndex)))
1517                  ((= index (the fixnum length))
1518                   (shrink-vector sequence jndex))
1519                (declare (fixnum index jndex))
1520                (setf (aref sequence jndex) (aref sequence index))))
1521           (declare (fixnum index jndex))
1522           (setf (aref sequence jndex) (aref sequence index))
1523           (if (= index (the fixnum (car losers)))
1524               (pop losers)
1525               (incf jndex))))
1526      (declare (fixnum index number-zapped terminus))
1527      (setq this-element (aref sequence index))
1528      (when ,pred
1529        (incf number-zapped)
1530        (push index losers))))
1531
1532 (sb!xc:defmacro normal-mumble-delete ()
1533   `(mumble-delete
1534     (if test-not
1535         (not (funcall test-not item (apply-key key (aref sequence index))))
1536         (funcall test item (apply-key key (aref sequence index))))))
1537
1538 (sb!xc:defmacro normal-mumble-delete-from-end ()
1539   `(mumble-delete-from-end
1540     (if test-not
1541         (not (funcall test-not item (apply-key key this-element)))
1542         (funcall test item (apply-key key this-element)))))
1543
1544 (sb!xc:defmacro list-delete (pred)
1545   `(let ((handle (cons nil sequence)))
1546      (declare (truly-dynamic-extent handle))
1547      (do* ((previous (nthcdr start handle))
1548            (current (cdr previous) (cdr current))
1549            (index start (1+ index))
1550            (number-zapped 0))
1551           ((or (= index end) (= number-zapped count))
1552            (cdr handle))
1553        (declare (index index number-zapped))
1554        (cond (,pred
1555               (rplacd previous (cdr current))
1556               (incf number-zapped))
1557              (t
1558               (pop previous))))))
1559
1560 (sb!xc:defmacro list-delete-from-end (pred)
1561   `(let* ((reverse (nreverse sequence))
1562           (handle (cons nil reverse)))
1563      (declare (truly-dynamic-extent handle))
1564      (do* ((previous (nthcdr (- length end) handle))
1565            (current (cdr previous) (cdr current))
1566            (index start (1+ index))
1567            (number-zapped 0))
1568           ((or (= index end) (= number-zapped count))
1569            (nreverse (cdr handle)))
1570        (declare (index index number-zapped))
1571        (cond (,pred
1572               (rplacd previous (cdr current))
1573               (incf number-zapped))
1574              (t
1575               (pop previous))))))
1576
1577 (sb!xc:defmacro normal-list-delete ()
1578   '(list-delete
1579     (if test-not
1580         (not (funcall test-not item (apply-key key (car current))))
1581         (funcall test item (apply-key key (car current))))))
1582
1583 (sb!xc:defmacro normal-list-delete-from-end ()
1584   '(list-delete-from-end
1585     (if test-not
1586         (not (funcall test-not item (apply-key key (car current))))
1587         (funcall test item (apply-key key (car current))))))
1588
1589 ) ; EVAL-WHEN
1590
1591 (define-sequence-traverser delete
1592     (item sequence &rest args &key from-end test test-not start
1593      end count key)
1594   "Return a sequence formed by destructively removing the specified ITEM from
1595   the given SEQUENCE."
1596   (declare (type fixnum start)
1597            (truly-dynamic-extent args))
1598   (declare (explicit-check sequence :result))
1599   (seq-dispatch-checking=>seq sequence
1600     (let ((end (or end length)))
1601       (declare (type index end))
1602       (if from-end
1603           (normal-list-delete-from-end)
1604           (normal-list-delete)))
1605     (let ((end (or end length)))
1606       (declare (type index end))
1607       (if from-end
1608           (normal-mumble-delete-from-end)
1609           (normal-mumble-delete)))
1610     (apply #'sb!sequence:delete item sequence args)))
1611
1612 (eval-when (:compile-toplevel :execute)
1613
1614 (sb!xc:defmacro if-mumble-delete ()
1615   `(mumble-delete
1616     (funcall predicate (apply-key key (aref sequence index)))))
1617
1618 (sb!xc:defmacro if-mumble-delete-from-end ()
1619   `(mumble-delete-from-end
1620     (funcall predicate (apply-key key this-element))))
1621
1622 (sb!xc:defmacro if-list-delete ()
1623   '(list-delete
1624     (funcall predicate (apply-key key (car current)))))
1625
1626 (sb!xc:defmacro if-list-delete-from-end ()
1627   '(list-delete-from-end
1628     (funcall predicate (apply-key key (car current)))))
1629
1630 ) ; EVAL-WHEN
1631
1632 (define-sequence-traverser delete-if
1633     (predicate sequence &rest args &key from-end start key end count)
1634   "Return a sequence formed by destructively removing the elements satisfying
1635   the specified PREDICATE from the given SEQUENCE."
1636   (declare (type fixnum start)
1637            (truly-dynamic-extent args))
1638   (declare (explicit-check sequence :result))
1639   (seq-dispatch-checking=>seq sequence
1640     (let ((end (or end length)))
1641       (declare (type index end))
1642       (if from-end
1643           (if-list-delete-from-end)
1644           (if-list-delete)))
1645     (let ((end (or end length)))
1646       (declare (type index end))
1647       (if from-end
1648           (if-mumble-delete-from-end)
1649           (if-mumble-delete)))
1650     (apply #'sb!sequence:delete-if predicate sequence args)))
1651
1652 (eval-when (:compile-toplevel :execute)
1653
1654 (sb!xc:defmacro if-not-mumble-delete ()
1655   `(mumble-delete
1656     (not (funcall predicate (apply-key key (aref sequence index))))))
1657
1658 (sb!xc:defmacro if-not-mumble-delete-from-end ()
1659   `(mumble-delete-from-end
1660     (not (funcall predicate (apply-key key this-element)))))
1661
1662 (sb!xc:defmacro if-not-list-delete ()
1663   '(list-delete
1664     (not (funcall predicate (apply-key key (car current))))))
1665
1666 (sb!xc:defmacro if-not-list-delete-from-end ()
1667   '(list-delete-from-end
1668     (not (funcall predicate (apply-key key (car current))))))
1669
1670 ) ; EVAL-WHEN
1671
1672 (define-sequence-traverser delete-if-not
1673     (predicate sequence &rest args &key from-end start end key count)
1674   "Return a sequence formed by destructively removing the elements not
1675   satisfying the specified PREDICATE from the given SEQUENCE."
1676   (declare (type fixnum start)
1677            (truly-dynamic-extent args))
1678   (declare (explicit-check sequence :result))
1679   (seq-dispatch-checking=>seq sequence
1680     (let ((end (or end length)))
1681       (declare (type index end))
1682       (if from-end
1683           (if-not-list-delete-from-end)
1684           (if-not-list-delete)))
1685     (let ((end (or end length)))
1686       (declare (type index end))
1687       (if from-end
1688           (if-not-mumble-delete-from-end)
1689           (if-not-mumble-delete)))
1690     (apply #'sb!sequence:delete-if-not predicate sequence args)))
1691 \f
1692 ;;;; REMOVE
1693
1694 (eval-when (:compile-toplevel :execute)
1695
1696 ;;; MUMBLE-REMOVE-MACRO does not include (removes) each element that
1697 ;;; satisfies the predicate.
1698 (sb!xc:defmacro mumble-remove-macro (bump left begin finish right pred)
1699   `(do ((index ,begin (,bump index))
1700         (result
1701          (do ((index ,left (,bump index))
1702               (result (%make-sequence-like sequence length)))
1703              ((= index (the fixnum ,begin)) result)
1704            (declare (fixnum index))
1705            (setf (aref result index) (aref sequence index))))
1706         (new-index ,begin)
1707         (number-zapped 0)
1708         (this-element))
1709        ((or (= index (the fixnum ,finish))
1710             (= number-zapped count))
1711         (do ((index index (,bump index))
1712              (new-index new-index (,bump new-index)))
1713             ((= index (the fixnum ,right)) (%shrink-vector result new-index))
1714           (declare (fixnum index new-index))
1715           (setf (aref result new-index) (aref sequence index))))
1716      (declare (fixnum index new-index number-zapped))
1717      (setq this-element (aref sequence index))
1718      (cond (,pred (incf number-zapped))
1719            (t (setf (aref result new-index) this-element)
1720               (setq new-index (,bump new-index))))))
1721
1722 (sb!xc:defmacro mumble-remove (pred)
1723   `(mumble-remove-macro 1+ 0 start end length ,pred))
1724
1725 (sb!xc:defmacro mumble-remove-from-end (pred)
1726   `(let ((sequence (copy-seq sequence)))
1727      (mumble-delete-from-end ,pred)))
1728
1729 (sb!xc:defmacro normal-mumble-remove ()
1730   `(mumble-remove
1731     (if test-not
1732         (not (funcall test-not item (apply-key key this-element)))
1733         (funcall test item (apply-key key this-element)))))
1734
1735 (sb!xc:defmacro normal-mumble-remove-from-end ()
1736   `(mumble-remove-from-end
1737     (if test-not
1738         (not (funcall test-not item (apply-key key this-element)))
1739         (funcall test item (apply-key key this-element)))))
1740
1741 (sb!xc:defmacro if-mumble-remove ()
1742   `(mumble-remove (funcall predicate (apply-key key this-element))))
1743
1744 (sb!xc:defmacro if-mumble-remove-from-end ()
1745   `(mumble-remove-from-end (funcall predicate (apply-key key this-element))))
1746
1747 (sb!xc:defmacro if-not-mumble-remove ()
1748   `(mumble-remove (not (funcall predicate (apply-key key this-element)))))
1749
1750 (sb!xc:defmacro if-not-mumble-remove-from-end ()
1751   `(mumble-remove-from-end
1752     (not (funcall predicate (apply-key key this-element)))))
1753
1754 ;;; LIST-REMOVE-MACRO does not include (removes) each element that satisfies
1755 ;;; the predicate.
1756 (sb!xc:defmacro list-remove-macro (pred reverse?)
1757   `(let* ((sequence ,(if reverse?
1758                          '(reverse (the list sequence))
1759                          'sequence))
1760           (%start ,(if reverse? '(- length end) 'start))
1761           (%end ,(if reverse? '(- length start) 'end))
1762           (splice (list nil))
1763           (tail (and (/= %end length)
1764                      (nthcdr %end sequence)))
1765           (results ,(if reverse?
1766                           ;; It's already copied by REVERSE, so it can
1767                           ;; be modified here
1768                           `(if (plusp %start)
1769                                (let* ((tail (nthcdr (1- %start) sequence))
1770                                       (remaining (cdr tail)))
1771                                  (setf (cdr tail) nil)
1772                                  (prog1 splice
1773                                    (rplacd splice sequence)
1774                                    (setf splice tail
1775                                          sequence remaining)))
1776                                splice)
1777                           `(do ((index 0 (1+ index))
1778                                 (before-start splice))
1779                                ((= index (the fixnum %start)) before-start)
1780                              (declare (fixnum index))
1781                              (setf splice
1782                                    (cdr (rplacd splice (list (pop sequence)))))))))
1783      (declare (truly-dynamic-extent splice))
1784      (do ((this-element)
1785           (number-zapped 0))
1786          ((cond ((eq tail sequence)
1787                  (rplacd splice tail)
1788                  t)
1789                 ((= number-zapped count)
1790                  (rplacd splice sequence)
1791                  t))
1792           ,(if reverse?
1793                '(nreverse (the list (cdr results)))
1794                '(cdr results)))
1795        (declare (index number-zapped))
1796        (setf this-element (pop sequence))
1797        (if ,pred
1798            (incf number-zapped)
1799            (setf splice (cdr (rplacd splice (list this-element))))))))
1800
1801 (sb!xc:defmacro list-remove (pred)
1802   `(list-remove-macro ,pred nil))
1803
1804 (sb!xc:defmacro list-remove-from-end (pred)
1805   `(list-remove-macro ,pred t))
1806
1807 (sb!xc:defmacro normal-list-remove ()
1808   `(list-remove
1809     (if test-not
1810         (not (funcall test-not item (apply-key key this-element)))
1811         (funcall test item (apply-key key this-element)))))
1812
1813 (sb!xc:defmacro normal-list-remove-from-end ()
1814   `(list-remove-from-end
1815     (if test-not
1816         (not (funcall test-not item (apply-key key this-element)))
1817         (funcall test item (apply-key key this-element)))))
1818
1819 (sb!xc:defmacro if-list-remove ()
1820   `(list-remove
1821     (funcall predicate (apply-key key this-element))))
1822
1823 (sb!xc:defmacro if-list-remove-from-end ()
1824   `(list-remove-from-end
1825     (funcall predicate (apply-key key this-element))))
1826
1827 (sb!xc:defmacro if-not-list-remove ()
1828   `(list-remove
1829     (not (funcall predicate (apply-key key this-element)))))
1830
1831 (sb!xc:defmacro if-not-list-remove-from-end ()
1832   `(list-remove-from-end
1833     (not (funcall predicate (apply-key key this-element)))))
1834
1835 ) ; EVAL-WHEN
1836
1837 (define-sequence-traverser remove
1838     (item sequence &rest args &key from-end test test-not start
1839      end count key)
1840   "Return a copy of SEQUENCE with elements satisfying the test (default is
1841    EQL) with ITEM removed."
1842   (declare (type fixnum start)
1843            (truly-dynamic-extent args))
1844   (declare (explicit-check sequence :result))
1845   (seq-dispatch-checking=>seq sequence
1846     (let ((end (or end length)))
1847       (declare (type index end))
1848       (if from-end
1849           (normal-list-remove-from-end)
1850           (normal-list-remove)))
1851     (let ((end (or end length)))
1852       (declare (type index end))
1853       (if from-end
1854           (normal-mumble-remove-from-end)
1855           (normal-mumble-remove)))
1856     (apply #'sb!sequence:remove item sequence args)))
1857
1858 (define-sequence-traverser remove-if
1859     (predicate sequence &rest args &key from-end start end count key)
1860   "Return a copy of sequence with elements satisfying PREDICATE removed."
1861   (declare (type fixnum start)
1862            (truly-dynamic-extent args))
1863   (declare (explicit-check sequence :result))
1864   (seq-dispatch-checking=>seq sequence
1865     (let ((end (or end length)))
1866       (declare (type index end))
1867       (if from-end
1868           (if-list-remove-from-end)
1869           (if-list-remove)))
1870     (let ((end (or end length)))
1871       (declare (type index end))
1872       (if from-end
1873           (if-mumble-remove-from-end)
1874           (if-mumble-remove)))
1875     (apply #'sb!sequence:remove-if predicate sequence args)))
1876
1877 (define-sequence-traverser remove-if-not
1878     (predicate sequence &rest args &key from-end start end count key)
1879   "Return a copy of sequence with elements not satisfying PREDICATE removed."
1880   (declare (type fixnum start)
1881            (truly-dynamic-extent args))
1882   (declare (explicit-check sequence :result))
1883   (seq-dispatch-checking=>seq sequence
1884     (let ((end (or end length)))
1885       (declare (type index end))
1886       (if from-end
1887           (if-not-list-remove-from-end)
1888           (if-not-list-remove)))
1889     (let ((end (or end length)))
1890       (declare (type index end))
1891       (if from-end
1892           (if-not-mumble-remove-from-end)
1893           (if-not-mumble-remove)))
1894     (apply #'sb!sequence:remove-if-not predicate sequence args)))
1895 \f
1896 ;;;; REMOVE-DUPLICATES
1897
1898 ;;; Remove duplicates from a list. If from-end, remove the later duplicates,
1899 ;;; not the earlier ones. Thus if we check from-end we don't copy an item
1900 ;;; if we look into the already copied structure (from after :start) and see
1901 ;;; the item. If we check from beginning we check into the rest of the
1902 ;;; original list up to the :end marker (this we have to do by running a
1903 ;;; do loop down the list that far and using our test.
1904 (defun list-remove-duplicates* (list test test-not start end key from-end)
1905   (declare (fixnum start)
1906            (list list))
1907   (let* ((result (list ())) ; Put a marker on the beginning to splice with.
1908          (splice result)
1909          (current list)
1910          (length (length list))
1911          (end (or end length))
1912          (whole (= end length))
1913          (hash (and (> (- end start) 20)
1914                     (not key)
1915                     (not test-not)
1916                     (hash-table-test-p test)
1917                     (make-hash-table :test test :size (- end start))))
1918          (tail (and (not whole)
1919                     (nthcdr end list))))
1920     (declare (truly-dynamic-extent result))
1921     (do ((index 0 (1+ index)))
1922         ((= index start))
1923       (declare (fixnum index))
1924       (setq splice (cdr (rplacd splice (list (car current)))))
1925       (setq current (cdr current)))
1926     (if hash
1927         (do ()
1928             ((eq current tail))
1929           ;; The hash table contains links from values that are
1930           ;; already in result to the cons cell *preceding* theirs
1931           ;; in the list.  That is, for each value v in the list,
1932           ;; v and (cadr (gethash v hash)) are equal under TEST.
1933           (let ((prev (gethash (car current) hash)))
1934             (cond
1935               ((not prev)
1936                (setf (gethash (car current) hash) splice)
1937                (setq splice (cdr (rplacd splice (list (car current))))))
1938               ((not from-end)
1939                (let* ((old (cdr prev))
1940                       (next (cdr old)))
1941                  (if next
1942                      (let ((next-val (car next)))
1943                        ;; (assert (eq (gethash next-val hash) old))
1944                        (setf (cdr prev) next
1945                              (gethash next-val hash) prev
1946                              (gethash (car current) hash) splice
1947                              splice (cdr (rplacd splice (list (car current))))))
1948                      (setf (car old) (car current)))))))
1949           (setq current (cdr current)))
1950         (let ((testp test) ;; for with-member-test
1951               (notp test-not))
1952           (with-member-test (member-test
1953                              ((and (not from-end)
1954                                    (not whole))
1955                               (if notp
1956                                   (if key
1957                                       (lambda (x y key test)
1958                                         (not (funcall (truly-the function test) x
1959                                                       (funcall (truly-the function key) y))))
1960                                       (lambda (x y key test)
1961                                         (declare (ignore key))
1962                                         (not (funcall (truly-the function test) x y))))
1963                                   (if key
1964                                       (lambda (x y key test)
1965                                         (funcall (truly-the function test) x
1966                                                  (funcall (truly-the function key) y)))
1967                                       (lambda (x y key test)
1968                                         (declare (ignore key))
1969                                         (funcall (truly-the function test) x y))))))
1970             (do ((copied (nthcdr start result)))
1971                 ((eq current tail))
1972               (let ((elt (car current)))
1973                 (when (cond (from-end
1974                              (not (funcall member-test elt (cdr copied) key test)))
1975                             (whole
1976                              (not (funcall member-test elt (cdr current) key test)))
1977                             (t
1978                              (do ((it (apply-key key elt))
1979                                   (l (cdr current) (cdr l)))
1980                                  ((eq l tail)
1981                                   t)
1982                                (when (funcall member-test it (car l) key test)
1983                                  (return)))))
1984                   (setf splice (cdr (rplacd splice (list elt))))))
1985               (pop current)))))
1986     (rplacd splice tail)
1987     (cdr result)))
1988
1989 (defun vector-remove-duplicates* (vector test test-not start end key from-end
1990                                          &optional (length (length vector)))
1991   (declare (vector vector) (fixnum start length))
1992   (when (null end) (setf end (length vector)))
1993   (let ((result (%make-sequence-like vector length))
1994         (index 0)
1995         (jndex start))
1996     (declare (fixnum index jndex))
1997     (do ()
1998         ((= index start))
1999       (setf (aref result index) (aref vector index))
2000       (setq index (1+ index)))
2001     (do ((elt))
2002         ((= index end))
2003       (setq elt (aref vector index))
2004       (unless (or (and from-end
2005                        (if test-not
2006                            (position (apply-key key elt) result
2007                                      :start start :end jndex
2008                                      :test-not test-not :key key)
2009                            (position (apply-key key elt) result
2010                                      :start start :end jndex
2011                                      :test test :key key)))
2012                   (and (not from-end)
2013                        (if test-not
2014                            (position (apply-key key elt) vector
2015                                      :start (1+ index) :end end
2016                                      :test-not test-not :key key)
2017                            (position (apply-key key elt) vector
2018                                      :start (1+ index) :end end
2019                                      :test test :key key))))
2020         (setf (aref result jndex) elt)
2021         (setq jndex (1+ jndex)))
2022       (setq index (1+ index)))
2023     (do ()
2024         ((= index length))
2025       (setf (aref result jndex) (aref vector index))
2026       (setq index (1+ index))
2027       (setq jndex (1+ jndex)))
2028     (%shrink-vector result jndex)))
2029
2030 (define-sequence-traverser remove-duplicates
2031     (sequence &rest args &key test test-not start end from-end key)
2032   "The elements of SEQUENCE are compared pairwise, and if any two match,
2033    the one occurring earlier is discarded, unless FROM-END is true, in
2034    which case the one later in the sequence is discarded. The resulting
2035    sequence is returned.
2036
2037    The :TEST-NOT argument is deprecated."
2038   (declare (fixnum start)
2039            (truly-dynamic-extent args))
2040   (declare (explicit-check sequence :result))
2041   (seq-dispatch-checking=>seq sequence
2042     (if sequence
2043         (list-remove-duplicates* sequence test test-not
2044                                  start end key from-end))
2045     (vector-remove-duplicates* sequence test test-not start end key from-end)
2046     (apply #'sb!sequence:remove-duplicates sequence args)))
2047 \f
2048 ;;;; DELETE-DUPLICATES
2049 (defun list-delete-duplicates* (list test test-not key from-end start end)
2050   (declare (index start)
2051            (list list))
2052   (let* ((handle (cons nil list))
2053          (from-end-start (and from-end
2054                               (nthcdr (1+ start) handle)))
2055          (length (length list))
2056          (end (or end length))
2057          (tail (and (/= length (truly-the fixnum end))
2058                     (nthcdr end list))))
2059     (declare (truly-dynamic-extent handle))
2060     (do* ((previous (nthcdr start handle))
2061           (current (cdr previous) (cdr current)))
2062          ((eq current tail)
2063           (cdr handle))
2064       (if (do ((end (if from-end
2065                         current
2066                         tail))
2067                (x (if from-end
2068                       from-end-start
2069                       (cdr current))
2070                   (cdr x)))
2071               ((eq x end))
2072             (if (if test-not
2073                     (not (funcall (truly-the function test-not)
2074                                   (apply-key-function key (car current))
2075                                   (apply-key-function key (car x))))
2076                     (funcall (truly-the function test)
2077                              (apply-key-function key (car current))
2078                              (apply-key-function key (car x))))
2079                 (return t)))
2080           (rplacd previous (cdr current))
2081           (pop previous)))))
2082
2083 (defun vector-delete-duplicates* (vector test test-not key from-end start end
2084                                          &optional (length (length vector)))
2085   (declare (vector vector) (fixnum start length))
2086   (when (null end) (setf end (length vector)))
2087   (do ((index start (1+ index))
2088        (jndex start))
2089       ((= index end)
2090        (do ((index index (1+ index))            ; copy the rest of the vector
2091             (jndex jndex (1+ jndex)))
2092            ((= index length)
2093             (shrink-vector vector jndex))
2094          (setf (aref vector jndex) (aref vector index))))
2095     (declare (fixnum index jndex))
2096     (setf (aref vector jndex) (aref vector index))
2097     (unless (if test-not
2098                 (position (apply-key key (aref vector index)) vector :key key
2099                           :start (if from-end start (1+ index))
2100                           :end (if from-end jndex end)
2101                           :test-not test-not)
2102                 (position (apply-key key (aref vector index)) vector :key key
2103                           :start (if from-end start (1+ index))
2104                           :end (if from-end jndex end)
2105                           :test test))
2106       (setq jndex (1+ jndex)))))
2107
2108 (define-sequence-traverser delete-duplicates
2109     (sequence &rest args &key test test-not start end from-end key)
2110   "The elements of SEQUENCE are examined, and if any two match, one is
2111    discarded. The resulting sequence, which may be formed by destroying the
2112    given sequence, is returned.
2113
2114    The :TEST-NOT argument is deprecated."
2115   (declare (truly-dynamic-extent args))
2116   (declare (explicit-check sequence :result))
2117   (seq-dispatch-checking=>seq sequence
2118     (when sequence
2119       (list-delete-duplicates* sequence test test-not
2120                                key from-end start end))
2121     (vector-delete-duplicates* sequence test test-not key from-end start end)
2122     (apply #'sb!sequence:delete-duplicates sequence args)))
2123 \f
2124 ;;;; SUBSTITUTE
2125
2126 (defun list-substitute* (pred new list start end count key test test-not old)
2127   (declare (fixnum start end count)
2128            (type (or null function) key)
2129            (optimize speed))
2130   (let* ((result (list nil))
2131          (test (or test-not test))
2132          (test-not (or test-not
2133                        (eq pred 'if-not)))
2134          elt
2135          (splice result)
2136          (list list))      ; Get a local list for a stepper.
2137     (declare (function test))
2138     (do ((index 0 (1+ index)))
2139         ((= index start))
2140       (declare (fixnum index))
2141       (setf splice (cdr (rplacd splice (list (car list))))
2142             list (cdr list)))
2143     (do ((index start (1+ index)))
2144         ((or (= index end) (null list) (= count 0)))
2145       (declare (fixnum index))
2146       (setf elt (car list)
2147             splice
2148             (cdr (rplacd splice
2149                          (list
2150                           (cond ((let* ((elt (apply-key key elt))
2151                                         (value (if (eq pred 'normal)
2152                                                    (funcall test old elt)
2153                                                    (funcall test elt))))
2154                                    (if test-not
2155                                        (not value)
2156                                        value))
2157                                  (decf count)
2158                                  new)
2159                                 (t elt)))))
2160             list (cdr list)))
2161     (do ()
2162         ((null list))
2163       (setf splice (cdr (rplacd splice (list (car list))))
2164             list (cdr list)))
2165     (cdr result)))
2166
2167 ;;; Replace old with new in sequence moving from left to right by incrementer
2168 ;;; on each pass through the loop. Called by all three substitute functions.
2169 (defun vector-substitute* (pred new sequence incrementer left right length
2170                            start end count key test test-not old)
2171   (declare (fixnum start count end incrementer right)
2172            (type (or null function) key))
2173   (let* ((result (make-vector-like sequence length))
2174          (getter (the function (svref %%data-vector-reffers%%
2175                                       (%other-pointer-widetag sequence))))
2176          (setter (the function (svref %%data-vector-setters%%
2177                                       (%other-pointer-widetag result))))
2178          (test (or test-not test))
2179          (test-not (or test-not
2180                        (eq pred 'if-not)))
2181          (index left))
2182     (declare (fixnum index)
2183              (function test))
2184     (do ()
2185         ((= index start))
2186       (funcall setter result index
2187                (funcall getter sequence index))
2188       (incf index incrementer))
2189     (do ((elt))
2190         ((or (= index end) (= count 0)))
2191       (setf elt (funcall getter sequence index))
2192       (funcall setter result index
2193                (cond ((let* ((elt (apply-key key elt))
2194                              (value (if (eq pred 'normal)
2195                                         (funcall test old elt)
2196                                         (funcall test elt))))
2197                         (if test-not
2198                             (not value)
2199                             value))
2200                       (decf count)
2201                       new)
2202                      (t elt)))
2203       (incf index incrementer))
2204     (do ()
2205         ((= index right))
2206       (funcall setter result index
2207                (funcall getter sequence index))
2208       (incf index incrementer))
2209     result))
2210
2211 (eval-when (:compile-toplevel :execute)
2212
2213 (sb!xc:defmacro subst-dispatch (pred)
2214   `(seq-dispatch-checking=>seq sequence
2215      (let ((end (or end length)))
2216        (declare (type index end))
2217        (if from-end
2218            (nreverse (list-substitute* ,pred
2219                                        new
2220                                        (reverse sequence)
2221                                        (- (the fixnum length)
2222                                           (the fixnum end))
2223                                        (- (the fixnum length)
2224                                           (the fixnum start))
2225                                        count key test test-not old))
2226            (list-substitute* ,pred
2227                              new sequence start end count key test test-not
2228                              old)))
2229
2230      (let ((end (or end length)))
2231        (declare (type index end))
2232        (if from-end
2233            (vector-substitute* ,pred new sequence -1 (1- (the fixnum length))
2234                                -1 length (1- (the fixnum end))
2235                                (1- (the fixnum start))
2236                                count key test test-not old)
2237            (vector-substitute* ,pred new sequence 1 0 length length
2238                                start end count key test test-not old)))
2239
2240     ;; FIXME: wow, this is an odd way to implement the dispatch.  PRED
2241     ;; here is (QUOTE [NORMAL|IF|IF-NOT]).  Not only is this pretty
2242     ;; pointless, but also LIST-SUBSTITUTE* and VECTOR-SUBSTITUTE*
2243     ;; dispatch once per element on PRED's run-time identity.
2244     ,(ecase (cadr pred)
2245        ((normal) `(apply #'sb!sequence:substitute new old sequence args))
2246        ((if) `(apply #'sb!sequence:substitute-if new predicate sequence args))
2247        ((if-not) `(apply #'sb!sequence:substitute-if-not new predicate sequence args)))))
2248 ) ; EVAL-WHEN
2249
2250 (define-sequence-traverser substitute
2251     (new old sequence &rest args &key from-end test test-not
2252          start count end key)
2253   "Return a sequence of the same kind as SEQUENCE with the same elements,
2254   except that all elements equal to OLD are replaced with NEW."
2255   (declare (type fixnum start)
2256            (explicit-check sequence :result)
2257            (truly-dynamic-extent args))
2258   (subst-dispatch 'normal))
2259 \f
2260 ;;;; SUBSTITUTE-IF, SUBSTITUTE-IF-NOT
2261
2262 (define-sequence-traverser substitute-if
2263     (new predicate sequence &rest args &key from-end start end count key)
2264   "Return a sequence of the same kind as SEQUENCE with the same elements
2265   except that all elements satisfying the PRED are replaced with NEW."
2266   (declare (type fixnum start)
2267            (explicit-check sequence :result)
2268            (truly-dynamic-extent args))
2269   (let ((test predicate)
2270         (test-not nil)
2271         old)
2272     (subst-dispatch 'if)))
2273
2274 (define-sequence-traverser substitute-if-not
2275     (new predicate sequence &rest args &key from-end start end count key)
2276   "Return a sequence of the same kind as SEQUENCE with the same elements
2277   except that all elements not satisfying the PRED are replaced with NEW."
2278   (declare (type fixnum start)
2279            (explicit-check sequence :result)
2280            (truly-dynamic-extent args))
2281   (let ((test predicate)
2282         (test-not nil)
2283         old)
2284     (subst-dispatch 'if-not)))
2285 \f
2286 ;;;; NSUBSTITUTE
2287
2288 (define-sequence-traverser nsubstitute
2289     (new old sequence &rest args &key from-end test test-not
2290          end count key start)
2291   "Return a sequence of the same kind as SEQUENCE with the same elements
2292   except that all elements equal to OLD are replaced with NEW. SEQUENCE
2293   may be destructively modified."
2294   (declare (type fixnum start)
2295            (truly-dynamic-extent args))
2296   (declare (explicit-check sequence :result))
2297   (seq-dispatch-checking=>seq sequence
2298     (let ((end (or end length)))
2299       (declare (type index end))
2300       (if from-end
2301           (nreverse (nlist-substitute*
2302                      new old (nreverse (the list sequence))
2303                      test test-not (- length end) (- length start)
2304                      count key))
2305           (nlist-substitute* new old sequence
2306                              test test-not start end count key)))
2307     (let ((end (or end length)))
2308       (declare (type index end))
2309       (if from-end
2310           (nvector-substitute* new old sequence -1
2311                                test test-not (1- end) (1- start) count key)
2312           (nvector-substitute* new old sequence 1
2313                                test test-not start end count key)))
2314     (apply #'sb!sequence:nsubstitute new old sequence args)))
2315
2316 (defun nlist-substitute* (new old sequence test test-not start end count key)
2317   (declare (fixnum start count end)
2318            (type (or null function) key))
2319   (do ((test (or test-not test))
2320        (list (nthcdr start sequence) (cdr list))
2321        (index start (1+ index)))
2322       ((or (= index end) (null list) (= count 0)) sequence)
2323     (declare (fixnum index)
2324              (function test))
2325     (let ((value (funcall test old (apply-key key (car list)))))
2326      (when (if test-not
2327                (not value)
2328                value)
2329        (rplaca list new)
2330        (decf count)))))
2331
2332 (defun nvector-substitute* (new old sequence incrementer
2333                             test test-not start end count key)
2334   (declare (fixnum start count end)
2335            (type (integer -1 1) incrementer)
2336            (type (or null function) key))
2337   (let* ((test (or test-not test))
2338          (tag (%other-pointer-widetag sequence))
2339          (getter (the function (svref %%data-vector-reffers%% tag)))
2340          (setter (the function (svref %%data-vector-setters%% tag))))
2341     (declare (function test))
2342     (do ((index start (+ index incrementer)))
2343         ((or (= index end) (= count 0)) sequence)
2344       (declare (fixnum index))
2345       (let* ((value (apply-key key (funcall getter sequence index)))
2346              (test (and (funcall test old value) 0)))
2347         (when (if test-not
2348                   (not test)
2349                   test)
2350           (funcall setter sequence index new)
2351           (decf count))))))
2352 \f
2353 ;;;; NSUBSTITUTE-IF, NSUBSTITUTE-IF-NOT
2354
2355 (define-sequence-traverser nsubstitute-if
2356     (new predicate sequence &rest args &key from-end start end count key)
2357   "Return a sequence of the same kind as SEQUENCE with the same elements
2358    except that all elements satisfying PREDICATE are replaced with NEW.
2359    SEQUENCE may be destructively modified."
2360   (declare (type fixnum start)
2361            (truly-dynamic-extent args))
2362   (declare (explicit-check sequence :result))
2363   (seq-dispatch-checking=>seq sequence
2364     (let ((end (or end length)))
2365       (declare (type index end))
2366       (if from-end
2367           (nreverse (nlist-substitute-if*
2368                      new predicate (nreverse (the list sequence))
2369                      (- length end) (- length start) count key))
2370           (nlist-substitute-if* new predicate sequence
2371                                 start end count key)))
2372     (let ((end (or end length)))
2373       (declare (type index end))
2374       (if from-end
2375           (nvector-substitute-if* new predicate sequence -1
2376                                   (1- end) (1- start) count key)
2377           (nvector-substitute-if* new predicate sequence 1
2378                                   start end count key)))
2379     (apply #'sb!sequence:nsubstitute-if new predicate sequence args)))
2380
2381 (defun nlist-substitute-if* (new test sequence start end count key)
2382   (declare (type fixnum start end count)
2383            (type (or null function) key)
2384            (type function test)) ; coercion is done by caller
2385   (do ((list (nthcdr start sequence) (cdr list))
2386        (index start (1+ index)))
2387       ((or (= index end) (null list) (= count 0)) sequence)
2388     (declare (fixnum index))
2389     (when (funcall test (apply-key key (car list)))
2390       (rplaca list new)
2391       (decf count))))
2392
2393 (defun nvector-substitute-if* (new test sequence incrementer
2394                                start end count key)
2395   (declare (type fixnum end count)
2396            (type (integer -1 1) incrementer)
2397            (type (or null function) key)
2398            (type function test)) ; coercion is done by caller
2399   (let* ((tag (%other-pointer-widetag sequence))
2400          (getter (the function (svref %%data-vector-reffers%% tag)))
2401          (setter (the function (svref %%data-vector-setters%% tag))))
2402     (do ((index start (+ index incrementer)))
2403         ((or (= index end) (= count 0)) sequence)
2404       (declare (fixnum index))
2405       (when (funcall test (apply-key key (funcall getter sequence index)))
2406         (funcall setter sequence index new)
2407         (decf count)))))
2408
2409 (define-sequence-traverser nsubstitute-if-not
2410     (new predicate sequence &rest args &key from-end start end count key)
2411   "Return a sequence of the same kind as SEQUENCE with the same elements
2412    except that all elements not satisfying PREDICATE are replaced with NEW.
2413    SEQUENCE may be destructively modified."
2414   (declare (type fixnum start)
2415            (truly-dynamic-extent args))
2416   (declare (explicit-check sequence :result))
2417   (seq-dispatch-checking=>seq sequence
2418     (let ((end (or end length)))
2419       (declare (fixnum end))
2420       (if from-end
2421           (nreverse (nlist-substitute-if-not*
2422                      new predicate (nreverse (the list sequence))
2423                      (- length end) (- length start) count key))
2424           (nlist-substitute-if-not* new predicate sequence
2425                                     start end count key)))
2426     (let ((end (or end length)))
2427       (declare (fixnum end))
2428       (if from-end
2429           (nvector-substitute-if-not* new predicate sequence -1
2430                                       (1- end) (1- start) count key)
2431           (nvector-substitute-if-not* new predicate sequence 1
2432                                       start end count key)))
2433     (apply #'sb!sequence:nsubstitute-if-not new predicate sequence args)))
2434
2435 (defun nlist-substitute-if-not* (new test sequence start end count key)
2436   (declare (type fixnum start end count)
2437            (type (or null function) key)
2438            (type function test))        ; coercion is done by caller
2439   (do ((list (nthcdr start sequence) (cdr list))
2440        (index start (1+ index)))
2441       ((or (= index end) (null list) (= count 0)) sequence)
2442     (declare (fixnum index))
2443     (when (not (funcall test (apply-key key (car list))))
2444       (rplaca list new)
2445       (decf count))))
2446
2447 (defun nvector-substitute-if-not* (new test sequence incrementer
2448                                    start end count key)
2449   (declare (type fixnum end count)
2450            (type (integer -1 1) incrementer)
2451            (type (or null function) key)
2452            (type function test))        ; coercion is done by caller
2453   (let* ((tag (%other-pointer-widetag sequence))
2454          (getter (the function (svref %%data-vector-reffers%% tag)))
2455          (setter (the function (svref %%data-vector-setters%% tag))))
2456     (do ((index start (+ index incrementer)))
2457         ((or (= index end) (= count 0)) sequence)
2458       (declare (fixnum index))
2459       (when (not (funcall test (apply-key key (funcall getter sequence index))))
2460         (funcall setter sequence index new)
2461         (decf count)))))
2462 \f
2463 ;;;; FIND, POSITION, and their -IF and -IF-NOT variants
2464
2465 (defun effective-find-position-test (test test-not)
2466   (effective-find-position-test test test-not))
2467 (defun effective-find-position-key (key)
2468   (effective-find-position-key key))
2469
2470 ;;; shared guts of out-of-line FIND, POSITION, FIND-IF, and POSITION-IF
2471 (macrolet (;; shared logic for defining %FIND-POSITION and
2472            ;; %FIND-POSITION-IF in terms of various inlineable cases
2473            ;; of the expression defined in FROB and VECTOR*-FROB
2474            (frobs (&optional bit-frob)
2475              `(seq-dispatch-checking sequence-arg
2476                (frob sequence-arg from-end)
2477                (with-array-data ((sequence sequence-arg :offset-var offset)
2478                                  (start start)
2479                                  (end end)
2480                                  :check-fill-pointer t)
2481                  (multiple-value-bind (f p)
2482                      (macrolet ((frob2 () `(if from-end
2483                                                (frob sequence t)
2484                                                (frob sequence nil))))
2485                        (typecase sequence
2486                          #!+sb-unicode
2487                          ((simple-array character (*)) (frob2))
2488                          ((simple-array base-char (*)) (frob2))
2489                          ,@(when bit-frob
2490                              `((simple-bit-vector
2491                                 (if (and (typep item 'bit)
2492                                          (eq #'identity key)
2493                                          (or (eq #'eq test)
2494                                              (eq #'eql test)
2495                                              (eq #'equal test)))
2496                                     (let ((p (%bit-position item sequence
2497                                                             from-end start end)))
2498                                       (if p
2499                                           (values item p)
2500                                           (values nil nil)))
2501                                     (vector*-frob sequence)))))
2502                          (t
2503                           (vector*-frob sequence))))
2504                    (declare (type (or index null) p))
2505                    (values f (and p (the index (- p offset))))))
2506                ;; EXTENDED-SEQUENCE is not allowed.
2507                )))
2508   (defun %find-position (item sequence-arg from-end start end key test)
2509     (declare (explicit-check sequence-arg))
2510     (macrolet ((frob (sequence from-end)
2511                  `(%find-position item ,sequence
2512                                   ,from-end start end key test))
2513                (vector*-frob (sequence)
2514                  `(%find-position-vector-macro item ,sequence
2515                                                from-end start end key test)))
2516       (frobs t)))
2517   (defun %find-position-if (predicate sequence-arg from-end start end key)
2518     (declare (explicit-check sequence-arg))
2519     (macrolet ((frob (sequence from-end)
2520                  `(%find-position-if predicate ,sequence
2521                                      ,from-end start end key))
2522                (vector*-frob (sequence)
2523                  `(%find-position-if-vector-macro predicate ,sequence
2524                                                   from-end start end key)))
2525       (frobs)))
2526   (defun %find-position-if-not (predicate sequence-arg from-end start end key)
2527     (declare (explicit-check sequence-arg))
2528     (macrolet ((frob (sequence from-end)
2529                  `(%find-position-if-not predicate ,sequence
2530                                          ,from-end start end key))
2531                (vector*-frob (sequence)
2532                  `(%find-position-if-not-vector-macro predicate ,sequence
2533                                                   from-end start end key)))
2534       (frobs))))
2535
2536 (defun find
2537     (item sequence &rest args &key from-end (start 0) end key test test-not)
2538   (declare (truly-dynamic-extent args))
2539   (declare (explicit-check sequence))
2540   (seq-dispatch-checking sequence
2541     (nth-value 0 (%find-position
2542                   item sequence from-end start end
2543                   (effective-find-position-key key)
2544                   (effective-find-position-test test test-not)))
2545     (nth-value 0 (%find-position
2546                   item sequence from-end start end
2547                   (effective-find-position-key key)
2548                   (effective-find-position-test test test-not)))
2549     (apply #'sb!sequence:find item sequence args)))
2550 (defun position
2551     (item sequence &rest args &key from-end (start 0) end key test test-not)
2552   (declare (truly-dynamic-extent args))
2553   (declare (explicit-check sequence))
2554   (seq-dispatch-checking sequence
2555     (nth-value 1 (%find-position
2556                   item sequence from-end start end
2557                   (effective-find-position-key key)
2558                   (effective-find-position-test test test-not)))
2559     (nth-value 1 (%find-position
2560                   item sequence from-end start end
2561                   (effective-find-position-key key)
2562                   (effective-find-position-test test test-not)))
2563     (apply #'sb!sequence:position item sequence args)))
2564
2565 (defun find-if (predicate sequence &rest args &key from-end (start 0) end key)
2566   (declare (truly-dynamic-extent args))
2567   (declare (explicit-check sequence))
2568   (seq-dispatch-checking sequence
2569     (nth-value 0 (%find-position-if
2570                   (%coerce-callable-to-fun predicate)
2571                   sequence from-end start end
2572                   (effective-find-position-key key)))
2573     (nth-value 0 (%find-position-if
2574                   (%coerce-callable-to-fun predicate)
2575                   sequence from-end start end
2576                   (effective-find-position-key key)))
2577     (apply #'sb!sequence:find-if predicate sequence args)))
2578 (defun position-if
2579     (predicate sequence &rest args &key from-end (start 0) end key)
2580   (declare (truly-dynamic-extent args))
2581   (declare (explicit-check sequence))
2582   (seq-dispatch-checking sequence
2583     (nth-value 1 (%find-position-if
2584                   (%coerce-callable-to-fun predicate)
2585                   sequence from-end start end
2586                   (effective-find-position-key key)))
2587     (nth-value 1 (%find-position-if
2588                   (%coerce-callable-to-fun predicate)
2589                   sequence from-end start end
2590                   (effective-find-position-key key)))
2591     (apply #'sb!sequence:position-if predicate sequence args)))
2592
2593 (defun find-if-not
2594     (predicate sequence &rest args &key from-end (start 0) end key)
2595   (declare (truly-dynamic-extent args))
2596   (declare (explicit-check sequence))
2597   (seq-dispatch-checking sequence
2598     (nth-value 0 (%find-position-if-not
2599                   (%coerce-callable-to-fun predicate)
2600                   sequence from-end start end
2601                   (effective-find-position-key key)))
2602     (nth-value 0 (%find-position-if-not
2603                   (%coerce-callable-to-fun predicate)
2604                   sequence from-end start end
2605                   (effective-find-position-key key)))
2606     (apply #'sb!sequence:find-if-not predicate sequence args)))
2607 (defun position-if-not
2608     (predicate sequence &rest args &key from-end (start 0) end key)
2609   (declare (truly-dynamic-extent args))
2610   (declare (explicit-check sequence))
2611   (seq-dispatch-checking sequence
2612     (nth-value 1 (%find-position-if-not
2613                   (%coerce-callable-to-fun predicate)
2614                   sequence from-end start end
2615                   (effective-find-position-key key)))
2616     (nth-value 1 (%find-position-if-not
2617                   (%coerce-callable-to-fun predicate)
2618                   sequence from-end start end
2619                   (effective-find-position-key key)))
2620     (apply #'sb!sequence:position-if-not predicate sequence args)))
2621 \f
2622 ;;;; COUNT-IF, COUNT-IF-NOT, and COUNT
2623
2624 (eval-when (:compile-toplevel :execute)
2625
2626 (sb!xc:defmacro vector-count-if (notp from-end-p predicate sequence)
2627   (let ((next-index (if from-end-p '(1- index) '(1+ index)))
2628         (pred `(funcall ,predicate (apply-key key (aref ,sequence index)))))
2629     `(let ((%start ,(if from-end-p '(1- end) 'start))
2630            (%end ,(if from-end-p '(1- start) 'end)))
2631       (do ((index %start ,next-index)
2632            (count 0))
2633           ((= index (the fixnum %end)) count)
2634         (declare (fixnum index count))
2635         (,(if notp 'unless 'when) ,pred
2636           (setq count (1+ count)))))))
2637
2638 (sb!xc:defmacro list-count-if (notp from-end-p predicate sequence)
2639   (let ((pred `(funcall ,predicate (apply-key key (pop sequence)))))
2640     `(let ((%start ,(if from-end-p '(- length end) 'start))
2641            (%end ,(if from-end-p '(- length start) 'end))
2642            (sequence ,(if from-end-p '(reverse sequence) 'sequence)))
2643       (do ((sequence (nthcdr %start ,sequence))
2644            (index %start (1+ index))
2645            (count 0))
2646           ((or (= index (the fixnum %end)) (null sequence)) count)
2647         (declare (fixnum index count))
2648         (,(if notp 'unless 'when) ,pred
2649           (setq count (1+ count)))))))
2650
2651
2652 ) ; EVAL-WHEN
2653
2654 (define-sequence-traverser count-if
2655     (pred sequence &rest args &key from-end start end key)
2656   "Return the number of elements in SEQUENCE satisfying PRED(el)."
2657   (declare (type fixnum start)
2658            (truly-dynamic-extent args))
2659   (declare (explicit-check sequence))
2660   (let ((pred (%coerce-callable-to-fun pred)))
2661     (seq-dispatch-checking sequence
2662       (let ((end (or end length)))
2663         (declare (type index end))
2664         (if from-end
2665             (list-count-if nil t pred sequence)
2666             (list-count-if nil nil pred sequence)))
2667       (let ((end (or end length)))
2668         (declare (type index end))
2669         (if from-end
2670             (vector-count-if nil t pred sequence)
2671             (vector-count-if nil nil pred sequence)))
2672       (apply #'sb!sequence:count-if pred sequence args))))
2673
2674 (define-sequence-traverser count-if-not
2675     (pred sequence &rest args &key from-end start end key)
2676   "Return the number of elements in SEQUENCE not satisfying TEST(el)."
2677   (declare (type fixnum start)
2678            (truly-dynamic-extent args))
2679   (declare (explicit-check sequence))
2680   (let ((pred (%coerce-callable-to-fun pred)))
2681     (seq-dispatch-checking sequence
2682       (let ((end (or end length)))
2683         (declare (type index end))
2684         (if from-end
2685             (list-count-if t t pred sequence)
2686             (list-count-if t nil pred sequence)))
2687       (let ((end (or end length)))
2688         (declare (type index end))
2689         (if from-end
2690             (vector-count-if t t pred sequence)
2691             (vector-count-if t nil pred sequence)))
2692       (apply #'sb!sequence:count-if-not pred sequence args))))
2693
2694 (define-sequence-traverser count
2695     (item sequence &rest args &key from-end start end
2696           key (test #'eql test-p) (test-not nil test-not-p))
2697   "Return the number of elements in SEQUENCE satisfying a test with ITEM,
2698    which defaults to EQL."
2699   (declare (type fixnum start)
2700            (truly-dynamic-extent args))
2701   (declare (explicit-check sequence))
2702   (when (and test-p test-not-p)
2703     ;; Use the same wording as EFFECTIVE-FIND-POSITION-TEST
2704     (error "can't specify both :TEST and :TEST-NOT"))
2705   (let ((%test (if test-not-p
2706                    (lambda (x)
2707                      (not (funcall test-not item x)))
2708                    (lambda (x)
2709                      (funcall test item x)))))
2710     (seq-dispatch-checking sequence
2711       (let ((end (or end length)))
2712         (declare (type index end))
2713         (if from-end
2714             (list-count-if nil t %test sequence)
2715             (list-count-if nil nil %test sequence)))
2716       (let ((end (or end length)))
2717         (declare (type index end))
2718         (if from-end
2719             (vector-count-if nil t %test sequence)
2720             (vector-count-if nil nil %test sequence)))
2721       (apply #'sb!sequence:count item sequence args))))
2722 \f
2723 ;;;; MISMATCH
2724
2725 (eval-when (:compile-toplevel :execute)
2726
2727 (sb!xc:defmacro match-vars (&rest body)
2728   `(let ((inc (if from-end -1 1))
2729          (start1 (if from-end (1- (the fixnum end1)) start1))
2730          (start2 (if from-end (1- (the fixnum end2)) start2))
2731          (end1 (if from-end (1- (the fixnum start1)) end1))
2732          (end2 (if from-end (1- (the fixnum start2)) end2)))
2733      (declare (fixnum inc start1 start2 end1 end2))
2734      ,@body))
2735
2736 (sb!xc:defmacro matchify-list ((sequence start length end) &body body)
2737   (declare (ignore end)) ;; ### Should END be used below?
2738   `(let ((,sequence (if from-end
2739                         (nthcdr (- (the fixnum ,length) (the fixnum ,start) 1)
2740                                 (reverse (the list ,sequence)))
2741                         (nthcdr ,start ,sequence))))
2742      (declare (type list ,sequence))
2743      ,@body))
2744
2745 ) ; EVAL-WHEN
2746
2747 (eval-when (:compile-toplevel :execute)
2748
2749 (sb!xc:defmacro if-mismatch (elt1 elt2)
2750   `(cond ((= (the fixnum index1) (the fixnum end1))
2751           (return (if (= (the fixnum index2) (the fixnum end2))
2752                       nil
2753                       (if from-end
2754                           (1+ (the fixnum index1))
2755                           (the fixnum index1)))))
2756          ((= (the fixnum index2) (the fixnum end2))
2757           (return (if from-end (1+ (the fixnum index1)) index1)))
2758          (test-not
2759           (if (funcall test-not (apply-key key ,elt1) (apply-key key ,elt2))
2760               (return (if from-end (1+ (the fixnum index1)) index1))))
2761          (t (if (not (funcall test (apply-key key ,elt1)
2762                               (apply-key key ,elt2)))
2763                 (return (if from-end (1+ (the fixnum index1)) index1))))))
2764
2765 (sb!xc:defmacro mumble-mumble-mismatch ()
2766   `(do ((index1 start1 (+ index1 (the fixnum inc)))
2767         (index2 start2 (+ index2 (the fixnum inc))))
2768        (())
2769      (declare (fixnum index1 index2))
2770      (if-mismatch (aref sequence1 index1) (aref sequence2 index2))))
2771
2772 (sb!xc:defmacro mumble-list-mismatch ()
2773   `(do ((index1 start1 (+ index1 (the fixnum inc)))
2774         (index2 start2 (+ index2 (the fixnum inc))))
2775        (())
2776      (declare (fixnum index1 index2))
2777      (if-mismatch (aref sequence1 index1) (pop sequence2))))
2778 \f
2779 (sb!xc:defmacro list-mumble-mismatch ()
2780   `(do ((index1 start1 (+ index1 (the fixnum inc)))
2781         (index2 start2 (+ index2 (the fixnum inc))))
2782        (())
2783      (declare (fixnum index1 index2))
2784      (if-mismatch (pop sequence1) (aref sequence2 index2))))
2785
2786 (sb!xc:defmacro list-list-mismatch ()
2787   `(do ((sequence1 sequence1)
2788         (sequence2 sequence2)
2789         (index1 start1 (+ index1 (the fixnum inc)))
2790         (index2 start2 (+ index2 (the fixnum inc))))
2791        (())
2792      (declare (fixnum index1 index2))
2793      (if-mismatch (pop sequence1) (pop sequence2))))
2794
2795 ) ; EVAL-WHEN
2796
2797 (define-sequence-traverser mismatch
2798     (sequence1 sequence2 &rest args &key from-end test test-not
2799      start1 end1 start2 end2 key)
2800   "The specified subsequences of SEQUENCE1 and SEQUENCE2 are compared
2801    element-wise. If they are of equal length and match in every element, the
2802    result is NIL. Otherwise, the result is a non-negative integer, the index
2803    within SEQUENCE1 of the leftmost position at which they fail to match; or,
2804    if one is shorter than and a matching prefix of the other, the index within
2805    SEQUENCE1 beyond the last position tested is returned. If a non-NIL
2806    :FROM-END argument is given, then one plus the index of the rightmost
2807    position in which the sequences differ is returned."
2808   (declare (type fixnum start1 start2))
2809   (declare (truly-dynamic-extent args))
2810   (declare (explicit-check sequence1 sequence2 :result))
2811   (seq-dispatch-checking sequence1
2812     (seq-dispatch-checking sequence2
2813      (return-from mismatch
2814       (let ((end1 (or end1 length1))
2815             (end2 (or end2 length2)))
2816         (declare (type index end1 end2))
2817         (match-vars
2818          (matchify-list (sequence1 start1 length1 end1)
2819            (matchify-list (sequence2 start2 length2 end2)
2820              (list-list-mismatch))))))
2821      (return-from mismatch
2822       (let ((end1 (or end1 length1))
2823             (end2 (or end2 length2)))
2824         (declare (type index end1 end2))
2825         (match-vars
2826          (matchify-list (sequence1 start1 length1 end1)
2827            (list-mumble-mismatch)))))
2828      nil)
2829     (seq-dispatch-checking sequence2
2830      (return-from mismatch
2831       (let ((end1 (or end1 length1))
2832             (end2 (or end2 length2)))
2833         (declare (type index end1 end2))
2834         (match-vars
2835          (matchify-list (sequence2 start2 length2 end2)
2836            (mumble-list-mismatch)))))
2837      (return-from mismatch
2838       (let ((end1 (or end1 length1))
2839             (end2 (or end2 length2)))
2840         (declare (type index end1 end2))
2841         (match-vars
2842          (mumble-mumble-mismatch))))
2843      nil)
2844     t)
2845   ;; If sequence1 is an extended-sequence, we know nothing about sequence2.
2846   ;; If sequence1 was a list or vector, then sequence2 is an extended-sequence
2847   ;; or not a sequence. Either way, check it.
2848   (the (or index null)
2849     (values (apply #'sb!sequence:mismatch sequence1
2850                    (the sequence sequence2) args))))
2851 \f
2852 ;;; search comparison functions
2853
2854 (eval-when (:compile-toplevel :execute)
2855
2856 ;;; Compare two elements and return if they don't match.
2857 (sb!xc:defmacro compare-elements (elt1 elt2)
2858   `(if test-not
2859        (if (funcall test-not (apply-key key ,elt1) (apply-key key ,elt2))
2860            (return nil)
2861            t)
2862        (if (not (funcall test (apply-key key ,elt1) (apply-key key ,elt2)))
2863            (return nil)
2864            t)))
2865
2866 (sb!xc:defmacro search-compare-list-list (main sub)
2867   `(do ((main ,main (cdr main))
2868         (jndex start1 (1+ jndex))
2869         (sub (nthcdr start1 ,sub) (cdr sub)))
2870        ((or (endp main) (endp sub) (<= end1 jndex))
2871         t)
2872      (declare (type (integer 0) jndex))
2873      (compare-elements (car sub) (car main))))
2874
2875 (sb!xc:defmacro search-compare-list-vector (main sub)
2876   `(do ((main ,main (cdr main))
2877         (index start1 (1+ index)))
2878        ((or (endp main) (= index end1)) t)
2879      (compare-elements (aref ,sub index) (car main))))
2880
2881 (sb!xc:defmacro search-compare-vector-list (main sub index)
2882   `(do ((sub (nthcdr start1 ,sub) (cdr sub))
2883         (jndex start1 (1+ jndex))
2884         (index ,index (1+ index)))
2885        ((or (<= end1 jndex) (endp sub)) t)
2886      (declare (type (integer 0) jndex))
2887      (compare-elements (car sub) (aref ,main index))))
2888
2889 (sb!xc:defmacro search-compare-vector-vector (main sub index)
2890   `(do ((index ,index (1+ index))
2891         (sub-index start1 (1+ sub-index)))
2892        ((= sub-index end1) t)
2893      (compare-elements (aref ,sub sub-index) (aref ,main index))))
2894
2895 (sb!xc:defmacro search-compare (main-type main sub index)
2896   (if (eq main-type 'list)
2897       `(seq-dispatch ,sub
2898          (search-compare-list-list ,main ,sub)
2899          (search-compare-list-vector ,main ,sub)
2900          ;; KLUDGE: just hack it together so that it works
2901          (return-from search (apply #'sb!sequence:search sequence1 sequence2 args)))
2902       `(seq-dispatch ,sub
2903          (search-compare-vector-list ,main ,sub ,index)
2904          (search-compare-vector-vector ,main ,sub ,index)
2905          (return-from search (apply #'sb!sequence:search sequence1 sequence2 args)))))
2906
2907 ) ; EVAL-WHEN
2908 \f
2909 ;;;; SEARCH
2910
2911 (eval-when (:compile-toplevel :execute)
2912
2913 (sb!xc:defmacro list-search (main sub)
2914   `(do ((main (nthcdr start2 ,main) (cdr main))
2915         (index2 start2 (1+ index2))
2916         (terminus (- end2 (the (integer 0) (- end1 start1))))
2917         (last-match ()))
2918        ((> index2 terminus) last-match)
2919      (declare (type (integer 0) index2))
2920      (if (search-compare list main ,sub index2)
2921          (if from-end
2922              (setq last-match index2)
2923              (return index2)))))
2924
2925 (sb!xc:defmacro vector-search (main sub)
2926   `(do ((index2 start2 (1+ index2))
2927         (terminus (- end2 (the (integer 0) (- end1 start1))))
2928         (last-match ()))
2929        ((> index2 terminus) last-match)
2930      (declare (type (integer 0) index2))
2931      (if (search-compare vector ,main ,sub index2)
2932          (if from-end
2933              (setq last-match index2)
2934              (return index2)))))
2935
2936 ) ; EVAL-WHEN
2937
2938 (define-sequence-traverser search
2939     (sequence1 sequence2 &rest args &key
2940      from-end test test-not start1 end1 start2 end2 key)
2941   (declare (type fixnum start1 start2)
2942            (truly-dynamic-extent args))
2943   (declare (explicit-check sequence2))
2944   (seq-dispatch-checking sequence2
2945     (let ((end1 (or end1 length1))
2946           (end2 (or end2 length2)))
2947       (declare (type index end1 end2))
2948       (list-search sequence2 sequence1))
2949     (let ((end1 (or end1 length1))
2950           (end2 (or end2 length2)))
2951       (declare (type index end1 end2))
2952       (vector-search sequence2 sequence1))
2953     (apply #'sb!sequence:search sequence1 sequence2 args)))
2954
2955 ;;; FIXME: this was originally in array.lisp; it might be better to
2956 ;;; put it back there, and make DOSEQUENCE and SEQ-DISPATCH be in
2957 ;;; a new early-seq.lisp file.
2958 (macrolet ((body (lambda-list endp-test start-recursion next-layer)
2959               `(let ((index 0))
2960                  (labels ((frob ,lambda-list
2961                             (cond (,endp-test
2962                                    (setf (aref vector index) contents)
2963                                    (incf index))
2964                                   (t
2965                                    (unless (typep contents 'sequence)
2966                                      (error "malformed :INITIAL-CONTENTS: ~S is not a ~
2967                                              sequence, but ~W more layer~:P needed."
2968                                             contents
2969                                             (- (length dimensions) axis)))
2970                                    (let ((k this-dimension)
2971                                          (l (length contents)))
2972                                      (unless (= k l)
2973                                        (error "malformed :INITIAL-CONTENTS: Dimension of ~
2974                                                axis ~W is ~W, but ~S is ~W long."
2975                                               axis k contents l)))
2976                                    (sb!sequence:dosequence (content contents)
2977                                      ,next-layer)))))
2978                    ,start-recursion))))
2979
2980   (defun fill-data-vector (vector dimensions initial-contents)
2981     (declare (explicit-check))
2982     (symbol-macrolet ((this-dimension (car dims)))
2983       (body (axis dims contents) (null dims)
2984             (frob 0 dimensions initial-contents)
2985             (frob (1+ axis) (cdr dims) content))))
2986
2987   ;; Identical to FILL-DATA-VECTOR but avoid reference
2988   ;; to DIMENSIONS as a list except in case of error.
2989   (defun fill-array (initial-contents array)
2990     (declare (explicit-check))
2991     (let ((rank (array-rank array))
2992           (vector (%array-data array)))
2993       (symbol-macrolet ((dimensions (array-dimensions array))
2994                         (this-dimension (%array-dimension array axis)))
2995         (body (axis contents) (= axis rank)
2996               (frob 0 initial-contents)
2997               (frob (1+ axis) content))))
2998     array))