X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;ds=sidebyside;f=src%2Fcompiler%2Fseqtran.lisp;h=0074e149bfe26e0ecc4653bea80be4a4a0d7b4cf;hb=94c003b32e49fc11a182d50c405ffa18183aa005;hp=28da4444f2e8ae243a78b073f999e5895baa30e1;hpb=f24a665895283c52443ed45bb3e07530f760bbfa;p=sbcl.git diff --git a/src/compiler/seqtran.lisp b/src/compiler/seqtran.lisp index 28da444..0074e14 100644 --- a/src/compiler/seqtran.lisp +++ b/src/compiler/seqtran.lisp @@ -291,7 +291,14 @@ (or end length) (sequence-bounding-indices-bad-error vector start end))))) -(defun specialized-list-seek-function-name (function-name key-functions variant) +(def!type eq-comparable-type () + '(or fixnum (not number))) + +;;; True if EQL comparisons involving type can be simplified to EQ. +(defun eq-comparable-type-p (type) + (csubtypep type (specifier-type 'eq-comparable-type))) + +(defun specialized-list-seek-function-name (function-name key-functions &optional variant) (or (find-symbol (with-output-to-string (s) ;; Write "%NAME-FUN1-FUN2-FUN3", etc. Not only is ;; this ever so slightly faster then FORMAT, this @@ -310,11 +317,13 @@ function-name key-functions variant))) (defun transform-list-item-seek (name item list key test test-not node) + (when (and test test-not) + (abort-ir1-transform "Both ~S and ~S supplied to ~S." :test :test-not name)) ;; If TEST is EQL, drop it. - (when (and test (lvar-for-named-function test 'eql)) + (when (and test (lvar-fun-is test '(eql))) (setf test nil)) ;; Ditto for KEY IDENTITY. - (when (and key (lvar-for-named-function key 'identity)) + (when (and key (lvar-fun-is key '(identity))) (setf key nil)) ;; Key can legally be NIL, but if it's NIL for sure we pretend it's ;; not there at all. If it might be NIL, make up a form to that @@ -330,15 +339,16 @@ (%coerce-callable-to-fun key) #'identity))) (t - (values key '(%coerce-callable-to-fun key)))))) - (let* ((c-test (cond ((and test (lvar-for-named-function test 'eq)) + (values key (ensure-lvar-fun-form key 'key)))))) + (let* ((c-test (cond ((and test (lvar-fun-is test '(eq))) (setf test nil) 'eq) ((and (not test) (not test-not)) (when (eq-comparable-type-p (lvar-type item)) 'eq)))) - (funs (remove nil (list (and key 'key) (cond (test 'test) - (test-not 'test-not))))) + (funs (delete nil (list (when key (list key 'key)) + (when test (list test 'test)) + (when test-not (list test-not 'test-not))))) (target-expr (if key '(%funcall key target) 'target)) (test-expr (cond (test `(%funcall test item ,target-expr)) (test-not `(not (%funcall test-not item ,target-expr))) @@ -348,42 +358,114 @@ (when tail `(if (let ((this ',(car tail))) ,(ecase name - (assoc - `(and this (let ((target (car this))) - ,test-expr))) + ((assoc rassoc) + (let ((cxx (if (eq name 'assoc) 'car 'cdr))) + `(and this (let ((target (,cxx this))) + ,test-expr)))) (member `(let ((target this)) ,test-expr)))) ',(ecase name - (assoc (car tail)) + ((assoc rassoc) (car tail)) (member tail)) ,(open-code (cdr tail))))) - (ensure-fun (fun) - (if (eq 'key fun) + (ensure-fun (args) + (if (eq 'key (second args)) key-form - `(%coerce-callable-to-fun ,fun)))) + (apply #'ensure-lvar-fun-form args)))) (let* ((cp (constant-lvar-p list)) (c-list (when cp (lvar-value list)))) - (cond ((and cp c-list (member name '(assoc member)) + (cond ((and cp c-list (member name '(assoc rassoc member)) (policy node (>= speed space))) - `(let ,(mapcar (lambda (fun) `(,fun ,(ensure-fun fun))) funs) + `(let ,(mapcar (lambda (fun) `(,(second fun) ,(ensure-fun fun))) funs) ,(open-code c-list))) ((and cp (not c-list)) - ;; constant nil list -- nothing to find! - nil) + ;; constant nil list + (if (eq name 'adjoin) + '(list item) + nil)) (t ;; specialized out-of-line version - `(,(specialized-list-seek-function-name name funs c-test) + `(,(specialized-list-seek-function-name name (mapcar #'second funs) c-test) item list ,@(mapcar #'ensure-fun funs))))))))) -(deftransform member ((item list &key key test test-not) * * :node node) - (transform-list-item-seek 'member item list key test test-not node)) - -(deftransform assoc ((item list &key key test test-not) * * :node node) - (transform-list-item-seek 'assoc item list key test test-not node)) - -(deftransform adjoin ((item list &key key test test-not) * * :node node) - (transform-list-item-seek 'adjoin item list key test test-not node)) +(defun transform-list-pred-seek (name pred list key node) + ;; If KEY is IDENTITY, drop it. + (when (and key (lvar-fun-is key '(identity))) + (setf key nil)) + ;; Key can legally be NIL, but if it's NIL for sure we pretend it's + ;; not there at all. If it might be NIL, make up a form to that + ;; ensures it is a function. + (multiple-value-bind (key key-form) + (when key + (let ((key-type (lvar-type key)) + (null-type (specifier-type 'null))) + (cond ((csubtypep key-type null-type) + (values nil nil)) + ((csubtypep null-type key-type) + (values key '(if key + (%coerce-callable-to-fun key) + #'identity))) + (t + (values key (ensure-lvar-fun-form key 'key)))))) + (let ((test-expr `(%funcall pred ,(if key '(%funcall key target) 'target))) + (pred-expr (ensure-lvar-fun-form pred 'pred))) + (when (member name '(member-if-not assoc-if-not rassoc-if-not)) + (setf test-expr `(not ,test-expr))) + (labels ((open-code (tail) + (when tail + `(if (let ((this ',(car tail))) + ,(ecase name + ((assoc-if assoc-if-not rassoc-if rassoc-if-not) + (let ((cxx (if (member name '(assoc-if assoc-if-not)) 'car 'cdr))) + `(and this (let ((target (,cxx this))) + ,test-expr)))) + ((member-if member-if-not) + `(let ((target this)) + ,test-expr)))) + ',(ecase name + ((assoc-if assoc-if-not rassoc-if rassoc-if-not) + (car tail)) + ((member-if member-if-not) + tail)) + ,(open-code (cdr tail)))))) + (let* ((cp (constant-lvar-p list)) + (c-list (when cp (lvar-value list)))) + (cond ((and cp c-list (policy node (>= speed space))) + `(let ((pred ,pred-expr) + ,@(when key `((key ,key-form)))) + ,(open-code c-list))) + ((and cp (not c-list)) + ;; constant nil list -- nothing to find! + nil) + (t + ;; specialized out-of-line version + `(,(specialized-list-seek-function-name name (when key '(key))) + ,pred-expr list ,@(when key (list key-form)))))))))) + +(macrolet ((def (name &optional if/if-not) + (let ((basic (symbolicate "%" name)) + (basic-eq (symbolicate "%" name "-EQ")) + (basic-key (symbolicate "%" name "-KEY")) + (basic-key-eq (symbolicate "%" name "-KEY-EQ"))) + `(progn + (deftransform ,name ((item list &key key test test-not) * * :node node) + (transform-list-item-seek ',name item list key test test-not node)) + (deftransform ,basic ((item list) (eq-comparable-type t)) + `(,',basic-eq item list)) + (deftransform ,basic-key ((item list) (eq-comparable-type t)) + `(,',basic-key-eq item list)) + ,@(when if/if-not + (let ((if-name (symbolicate name "-IF")) + (if-not-name (symbolicate name "-IF-NOT"))) + `((deftransform ,if-name ((pred list &key key) * * :node node) + (transform-list-pred-seek ',if-name pred list key node)) + (deftransform ,if-not-name ((pred list &key key) * * :node node) + (transform-list-pred-seek ',if-not-name pred list key node))))))))) + (def adjoin) + (def assoc t) + (def member t) + (def rassoc t)) (deftransform memq ((item list) (t (constant-arg list))) (labels ((rec (tail) @@ -436,9 +518,110 @@ (vector t &key (:start t) (:end t)) * :node node) - (let ((type (lvar-type seq)) - (element-type (type-specifier (extract-upgraded-element-type seq)))) - (cond ((and (neq '* element-type) (policy node (> speed space))) + (let* ((type (lvar-type seq)) + (element-ctype (array-type-upgraded-element-type type)) + (element-type (type-specifier element-ctype)) + (saetp (unless (eq *wild-type* element-ctype) + (find-saetp-by-ctype element-ctype)))) + (cond ((eq *wild-type* element-ctype) + (delay-ir1-transform node :constraint) + `(vector-fill* seq item start end)) + ((and saetp (sb!vm::valid-bit-bash-saetp-p saetp)) + (let* ((n-bits (sb!vm:saetp-n-bits saetp)) + (basher-name (format nil "UB~D-BASH-FILL" n-bits)) + (basher (or (find-symbol basher-name + (load-time-value (find-package :sb!kernel))) + (abort-ir1-transform + "Unknown fill basher, please report to sbcl-devel: ~A" + basher-name))) + (kind (cond ((sb!vm:saetp-fixnum-p saetp) :tagged) + ((member element-type '(character base-char)) :char) + ((eq element-type 'single-float) :single-float) + #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or)) + ((eq element-type 'double-float) :double-float) + #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or)) + ((equal element-type '(complex single-float)) + :complex-single-float) + (t + (aver (integer-type-p element-ctype)) + :bits))) + ;; BASH-VALUE is a word that we can repeatedly smash + ;; on the array: for less-than-word sized elements it + ;; contains multiple copies of the fill item. + (bash-value + (if (constant-lvar-p item) + (let ((tmp (lvar-value item))) + (unless (ctypep tmp element-ctype) + (abort-ir1-transform "~S is not ~S" tmp element-type)) + (let* ((bits + (ldb (byte n-bits 0) + (ecase kind + (:tagged + (ash tmp sb!vm:n-fixnum-tag-bits)) + (:char + (char-code tmp)) + (:bits + tmp) + (:single-float + (single-float-bits tmp)) + #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or)) + (:double-float + (logior (ash (double-float-high-bits tmp) 32) + (double-float-low-bits tmp))) + #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or)) + (:complex-single-float + (logior (ash (single-float-bits (imagpart tmp)) 32) + (ldb (byte 32 0) + (single-float-bits (realpart tmp)))))))) + (res bits)) + (loop for i of-type sb!vm:word from n-bits by n-bits + until (= i sb!vm:n-word-bits) + do (setf res (ldb (byte sb!vm:n-word-bits 0) + (logior res (ash bits i))))) + res)) + (progn + (delay-ir1-transform node :constraint) + `(let* ((bits (ldb (byte ,n-bits 0) + ,(ecase kind + (:tagged + `(ash item ,sb!vm:n-fixnum-tag-bits)) + (:char + `(char-code item)) + (:bits + `item) + (:single-float + `(single-float-bits item)) + #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or)) + (:double-float + `(logior (ash (double-float-high-bits item) 32) + (double-float-low-bits item))) + #!+#.(cl:if (cl:= 64 sb!vm:n-word-bits) '(and) '(or)) + (:complex-single-float + `(logior (ash (single-float-bits (imagpart item)) 32) + (ldb (byte 32 0) + (single-float-bits (realpart item)))))))) + (res bits)) + (declare (type sb!vm:word res)) + ,@(unless (= sb!vm:n-word-bits n-bits) + `((loop for i of-type sb!vm:word from ,n-bits by ,n-bits + until (= i sb!vm:n-word-bits) + do (setf res + (ldb (byte ,sb!vm:n-word-bits 0) + (logior res (ash bits (truly-the (integer 0 ,(- sb!vm:n-word-bits n-bits)) i)))))))) + res))))) + (values + `(with-array-data ((data seq) + (start start) + (end end) + :check-fill-pointer t) + (declare (type (simple-array ,element-type 1) data)) + (declare (type index start end)) + (declare (optimize (safety 0) (speed 3)) + (muffle-conditions compiler-note)) + (,basher ,bash-value data start (- end start)) + seq) + `((declare (type ,element-type item)))))) + ((policy node (> speed space)) (values `(with-array-data ((data seq) (start start) @@ -467,34 +650,6 @@ :start start :end (%check-generic-sequence-bounds seq start end))) -;;;; utilities - -;;; Return true if LVAR's only use is a non-NOTINLINE reference to a -;;; global function with one of the specified NAMES. -(defun lvar-fun-is (lvar names) - (declare (type lvar lvar) (list names)) - (let ((use (lvar-uses lvar))) - (and (ref-p use) - (let ((leaf (ref-leaf use))) - (and (global-var-p leaf) - (eq (global-var-kind leaf) :global-function) - (not (null (member (leaf-source-name leaf) names - :test #'equal)))))))) - -;;; If LVAR is a constant lvar, the return the constant value. If it -;;; is null, then return default, otherwise quietly give up the IR1 -;;; transform. -;;; -;;; ### Probably should take an ARG and flame using the NAME. -(defun constant-value-or-lose (lvar &optional default) - (declare (type (or lvar null) lvar)) - (cond ((not lvar) default) - ((constant-lvar-p lvar) - (lvar-value lvar)) - (t - (give-up-ir1-transform)))) - - ;;;; hairy sequence transforms ;;; FIXME: no hairy sequence transforms in SBCL? @@ -573,20 +728,6 @@ (def!constant vector-data-bit-offset (* sb!vm:vector-data-offset sb!vm:n-word-bits)) -(eval-when (:compile-toplevel) -(defun valid-bit-bash-saetp-p (saetp) - ;; BIT-BASHing isn't allowed on simple vectors that contain pointers - (and (not (eq t (sb!vm:saetp-specifier saetp))) - ;; Disallowing (VECTOR NIL) also means that we won't transform - ;; sequence functions into bit-bashing code and we let the - ;; generic sequence functions signal errors if necessary. - (not (zerop (sb!vm:saetp-n-bits saetp))) - ;; Due to limitations with the current BIT-BASHing code, we can't - ;; BIT-BASH reliably on arrays whose element types are larger - ;; than the word size. - (<= (sb!vm:saetp-n-bits saetp) sb!vm:n-word-bits))) -) ; EVAL-WHEN - ;;; FIXME: In the copy loops below, we code the loops in a strange ;;; fashion: ;;; @@ -624,57 +765,50 @@ ;;; you tweak it, make sure that you compare the disassembly, if not the ;;; performance of, the functions implementing string streams ;;; (e.g. SB!IMPL::STRING-OUCH). -(eval-when (:compile-toplevel :load-toplevel :execute) +(eval-when (#-sb-xc :compile-toplevel :load-toplevel :execute) (defun make-replace-transform (saetp sequence-type1 sequence-type2) `(deftransform replace ((seq1 seq2 &key (start1 0) (start2 0) end1 end2) (,sequence-type1 ,sequence-type2 &rest t) ,sequence-type1 :node node) - ,(cond - ((and saetp (valid-bit-bash-saetp-p saetp)) nil) - ;; If the sequence types are different, SEQ1 and SEQ2 must - ;; be distinct arrays, and we can open code the copy loop. - ((not (eql sequence-type1 sequence-type2)) nil) - ;; If we're not bit-bashing, only allow cases where we - ;; can determine the order of copying up front. (There - ;; are actually more cases we can handle if we know the - ;; amount that we're copying, but this handles the - ;; common cases.) - (t '(unless (= (constant-value-or-lose start1 0) - (constant-value-or-lose start2 0)) - (give-up-ir1-transform)))) `(let* ((len1 (length seq1)) (len2 (length seq2)) (end1 (or end1 len1)) (end2 (or end2 len2)) - (replace-len1 (- end1 start1)) - (replace-len2 (- end2 start2))) + (replace-len (min (- end1 start1) (- end2 start2)))) ,(unless (policy node (= safety 0)) `(progn - (unless (<= 0 start1 end1 len1) - (sequence-bounding-indices-bad-error seq1 start1 end1)) - (unless (<= 0 start2 end2 len2) - (sequence-bounding-indices-bad-error seq2 start2 end2)))) + (unless (<= 0 start1 end1 len1) + (sequence-bounding-indices-bad-error seq1 start1 end1)) + (unless (<= 0 start2 end2 len2) + (sequence-bounding-indices-bad-error seq2 start2 end2)))) ,',(cond - ((and saetp (valid-bit-bash-saetp-p saetp)) - (let* ((n-element-bits (sb!vm:saetp-n-bits saetp)) - (bash-function (intern (format nil "UB~D-BASH-COPY" - n-element-bits) - (find-package "SB!KERNEL")))) - `(funcall (function ,bash-function) seq2 start2 - seq1 start1 (min replace-len1 replace-len2)))) - (t - ;; We can expand the loop inline here because we - ;; would have given up the transform (see above) - ;; if we didn't have constant matching start - ;; indices. - '(do ((i start1 (1+ i)) - (j start2 (1+ j)) - (end (+ start1 - (min replace-len1 replace-len2)))) - ((>= i end)) - (declare (optimize (insert-array-bounds-checks 0))) - (setf (aref seq1 i) (aref seq2 j))))) + ((and saetp (sb!vm:valid-bit-bash-saetp-p saetp)) + (let* ((n-element-bits (sb!vm:saetp-n-bits saetp)) + (bash-function (intern (format nil "UB~D-BASH-COPY" + n-element-bits) + (find-package "SB!KERNEL")))) + `(funcall (function ,bash-function) seq2 start2 + seq1 start1 replace-len))) + (t + `(if (and + ;; If the sequence types are different, SEQ1 and + ;; SEQ2 must be distinct arrays. + ,(eql sequence-type1 sequence-type2) + (eq seq1 seq2) (> start1 start2)) + (do ((i (truly-the index (+ start1 replace-len -1)) + (1- i)) + (j (truly-the index (+ start2 replace-len -1)) + (1- j))) + ((< i start1)) + (declare (optimize (insert-array-bounds-checks 0))) + (setf (aref seq1 i) (aref seq2 j))) + (do ((i start1 (1+ i)) + (j start2 (1+ j)) + (end (+ start1 replace-len))) + ((>= i end)) + (declare (optimize (insert-array-bounds-checks 0))) + (setf (aref seq1 i) (aref seq2 j)))))) seq1)))) (macrolet @@ -948,67 +1082,77 @@ ;;; this transform to non-strings, but I chose to just do the case that ;;; should cover 95% of CONCATENATE performance complaints for now. ;;; -- JES, 2007-11-17 +;;; +;;; Only handle the simple result type cases. If somebody does (CONCATENATE +;;; '(STRING 6) ...) their code won't be optimized, but nobody does that in +;;; practice. (deftransform concatenate ((result-type &rest lvars) - (symbol &rest sequence) - * - :policy (> speed space)) - (unless (constant-lvar-p result-type) - (give-up-ir1-transform)) - (let* ((element-type (let ((type (lvar-value result-type))) - ;; Only handle the simple result type cases. If - ;; somebody does (CONCATENATE '(STRING 6) ...) - ;; their code won't be optimized, but nobody does - ;; that in practice. - (case type - ((string simple-string) 'character) - ((base-string simple-base-string) 'base-char) - (t (give-up-ir1-transform))))) - (vars (loop for x in lvars collect (gensym))) - (lvar-values (loop for lvar in lvars - collect (when (constant-lvar-p lvar) - (lvar-value lvar)))) - (lengths - (loop for value in lvar-values - for var in vars - collect (if value - (length value) - `(sb!impl::string-dispatch ((simple-array * (*)) - sequence) - ,var - (declare (muffle-conditions compiler-note)) - (length ,var)))))) - `(apply - (lambda ,vars - (declare (ignorable ,@vars)) - (let* ((.length. (+ ,@lengths)) - (.pos. 0) - (.string. (make-string .length. :element-type ',element-type))) - (declare (type index .length. .pos.) - (muffle-conditions compiler-note)) - ,@(loop for value in lvar-values - for var in vars - collect (if (stringp value) - ;; Fold the array reads for constant arguments - `(progn - ,@(loop for c across value - collect `(setf (aref .string. - .pos.) ,c) - collect `(incf .pos.))) - `(sb!impl::string-dispatch - (#!+sb-unicode - (simple-array character (*)) - (simple-array base-char (*)) - t) - ,var - (replace .string. ,var :start1 .pos.) - (incf .pos. (length ,var))))) - .string.)) - lvars))) + ((constant-arg + (member string simple-string base-string simple-base-string)) + &rest sequence) + * :node node) + (let ((vars (loop for x in lvars collect (gensym))) + (type (lvar-value result-type))) + (if (policy node (<= speed space)) + ;; Out-of-line + `(lambda (.dummy. ,@vars) + (declare (ignore .dummy.)) + ,(ecase type + ((string simple-string) + `(%concatenate-to-string ,@vars)) + ((base-string simple-base-string) + `(%concatenate-to-base-string ,@vars)))) + ;; Inline + (let* ((element-type (ecase type + ((string simple-string) 'character) + ((base-string simple-base-string) 'base-char))) + (lvar-values (loop for lvar in lvars + collect (when (constant-lvar-p lvar) + (lvar-value lvar)))) + (lengths + (loop for value in lvar-values + for var in vars + collect (if value + (length value) + `(sb!impl::string-dispatch ((simple-array * (*)) + sequence) + ,var + (declare (muffle-conditions compiler-note)) + (length ,var)))))) + `(apply + (lambda ,vars + (declare (ignorable ,@vars)) + (let* ((.length. (+ ,@lengths)) + (.pos. 0) + (.string. (make-string .length. :element-type ',element-type))) + (declare (type index .length. .pos.) + (muffle-conditions compiler-note)) + ,@(loop for value in lvar-values + for var in vars + collect (if (stringp value) + ;; Fold the array reads for constant arguments + `(progn + ,@(loop for c across value + collect `(setf (aref .string. + .pos.) ,c) + collect `(incf .pos.))) + `(sb!impl::string-dispatch + (#!+sb-unicode + (simple-array character (*)) + (simple-array base-char (*)) + t) + ,var + (replace .string. ,var :start1 .pos.) + (incf .pos. (length ,var))))) + .string.)) + lvars))))) ;;;; CONS accessor DERIVE-TYPE optimizers (defoptimizer (car derive-type) ((cons)) - (let ((type (lvar-type cons)) + ;; This and CDR needs to use LVAR-CONSERVATIVE-TYPE because type inference + ;; gets confused by things like (SETF CAR). + (let ((type (lvar-conservative-type cons)) (null-type (specifier-type 'null))) (cond ((eq type null-type) null-type) @@ -1016,7 +1160,7 @@ (cons-type-car-type type))))) (defoptimizer (cdr derive-type) ((cons)) - (let ((type (lvar-type cons)) + (let ((type (lvar-conservative-type cons)) (null-type (specifier-type 'null))) (cond ((eq type null-type) null-type) @@ -1060,31 +1204,31 @@ (sequence-bounding-indices-bad-error sequence start end) (values find position))) - (let ((key-i (funcall key i))) - (when (and end (>= index end)) - (return (values find position))) - (when (>= index start) + (when (and end (>= index end)) + (return (values find position))) + (when (>= index start) + (let ((key-i (funcall key i))) (,',condition (funcall predicate key-i) - ;; This hack of dealing with non-NIL - ;; FROM-END for list data by iterating - ;; forward through the list and keeping - ;; track of the last time we found a match - ;; might be more screwy than what the user - ;; expects, but it seems to be allowed by - ;; the ANSI standard. (And if the user is - ;; screwy enough to ask for FROM-END - ;; behavior on list data, turnabout is - ;; fair play.) - ;; - ;; It's also not enormously efficient, - ;; calling PREDICATE and KEY more often - ;; than necessary; but all the - ;; alternatives seem to have their own - ;; efficiency problems. - (if from-end - (setf find i - position index) - (return (values i index)))))) + ;; This hack of dealing with non-NIL + ;; FROM-END for list data by iterating + ;; forward through the list and keeping + ;; track of the last time we found a + ;; match might be more screwy than what + ;; the user expects, but it seems to be + ;; allowed by the ANSI standard. (And + ;; if the user is screwy enough to ask + ;; for FROM-END behavior on list data, + ;; turnabout is fair play.) + ;; + ;; It's also not enormously efficient, + ;; calling PREDICATE and KEY more often + ;; than necessary; but all the + ;; alternatives seem to have their own + ;; efficiency problems. + (if from-end + (setf find i + position index) + (return (values i index)))))) (incf index)))))) (def %find-position-if when) (def %find-position-if-not unless)) @@ -1215,6 +1359,30 @@ '(%find-position-vector-macro item sequence from-end start end key test)) +(deftransform %find-position ((item sequence from-end start end key test) + (character string t t t function function) + * + :policy (> speed space)) + (if (eq '* (upgraded-element-type-specifier sequence)) + (let ((form + `(sb!impl::string-dispatch ((simple-array character (*)) + (simple-array base-char (*)) + (simple-array nil (*))) + sequence + (%find-position item sequence from-end start end key test)))) + (if (csubtypep (lvar-type sequence) (specifier-type 'simple-string)) + form + ;; Otherwise we'd get three instances of WITH-ARRAY-DATA from + ;; %FIND-POSITION. + `(with-array-data ((sequence sequence :offset-var offset) + (start start) + (end end) + :check-fill-pointer t) + (multiple-value-bind (elt index) ,form + (values elt (when (fixnump index) (- index offset))))))) + ;; The type is known exactly, other transforms will take care of it. + (give-up-ir1-transform))) + ;;; logic to unravel :TEST, :TEST-NOT, and :KEY options in FIND, ;;; POSITION-IF, etc. (define-source-transform effective-find-position-test (test test-not)