| blob | 4fc525108abbbfe2c4edd0b15631da37520999ec |
1 ;;;; optimizers for list and sequence functions
3 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; more information.
5 ;;;;
6 ;;;; This software is derived from the CMU CL system, which was
7 ;;;; written at Carnegie Mellon University and released into the
8 ;;;; public domain. The software is in the public domain and is
9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
10 ;;;; files for more information.
14 ;;; Regarding several reader-conditionalized MUFFLE-CONDITION declarations
15 ;;; throughout this file, here's why: Transforms produce sexprs that as far
16 ;;; as the compiler is concerned could have been user-supplied.
17 ;;; In as much as the forms mention a type-name, that name had best be
18 ;;; recognized, or else it's a style-warning (or worse).
19 ;;; And in cross-compilation, COMPILER-NOTE isn't known early enough for
20 ;;; the transforms in this file to refer to a known type.
21 ;;; But mysteriously the xc would report a style-warning about COMPILER-NOTE
22 ;;; - or any descendant - being unknown, and then go on with life.
23 ;;; How was this possible? Well, it's only trying to _parse_ the type
24 ;;; on account of the declarations saying to muffle things of that type.
25 ;;; Indeed the declaration merits a warning.
26 ;;; But this is an extremely sad and confusing state of affairs,
27 ;;; because while we expect some CODE-DELETION-NOTEs, we don't expect to see
28 ;;; that CODE-DELETION-NOTE is an undefined type.
29 ;;; Alternatively, we could invent DEFINE!-CONDITION which would cause
30 ;;; the cross-compiler to be born knowing all the required types.
31 ;;; Moreover, it would be nice if some of the declarations were commented
32 ;;; with their reason for existence.
34 \f
35 ;;;; mapping onto lists: the MAPFOO functions
37 ;; This expander allows a compiler-macro for FN to take effect by eliding
38 ;; a LET binding of it. Attempting to self-optimize like that isn't the usual
39 ;; SBCL way, however this is a countermeasure to an inhibition of a later
40 ;; optimization, and it is not an onerous change to the expander.
41 ;; We've gone to the trouble of inlining MAPfoo, but the inlined code
42 ;; prevented use of a compiler-macro because %FUNCALL (as opposed to FUNCALL)
43 ;; is not recognized. "Fixing" the compiler to understand %FUNCALL being
44 ;; the same isn't enough: the funarg must be a literal form because we can't
45 ;; know that a variable arg is a never-modified binding of 'F or #'F
46 ;; until IR1 has figured that out, at which point it is too late.
47 ;; [However, see lp# 632368 which asks for something like that.]
48 ;;
49 ;; Also, you might think there to be a subtle difference in behavior from
50 ;; delaying the reference to #'F versus referencing it once. But there is no
51 ;; difference - either way will use the #<fdefn> of F in the call.
52 ;; Of course, it would be ridiculously unportable to to rely on the
53 ;; fact that F can be changed (for its next call) while funcalling it.
54 ;;
61 arglists
72 (:nconc
76 ;; MUFFLE- is not injected when cross-compiling.
77 ;; See top of file for explanation.
79 #-sb-xc-host
86 (:list
90 ;; MUFFLE- is not injected when cross-compiling.
91 ;; See top of file for explanation.
93 #-sb-xc-host
98 (,endtest
101 ;; Accumulate using %RPLACD. RPLACD becomes (SETF CDR)
102 ;; which becomes %RPLACD but relies on "defsetfs".
103 ;; This is for effect, not value, so makes no difference.
105 ;; 0 is not written to the heap
130 \f
131 ;;;; mapping onto sequences: the MAP function
133 ;;; MAP is %MAP plus a check to make sure that any length specified in
134 ;;; the result type matches the actual result. We also wrap it in a
135 ;;; TRULY-THE for the most specific type we can determine.
140 ;; what we know about the type of the result. (Note that the
141 ;; "result type" argument is not necessarily the type of the
142 ;; result, since NIL means the result has NULL type.)
144 'consed-sequence
148 'null
149 result-type-arg-value)))))
153 ;; ANSI requires the length-related type check only
154 ;; when the SAFETY quality is 3... in other cases, we
155 ;; skip it, because it could be expensive.
156 bare)
159 result-type-arg))
162 result-type)))
169 bare
172 ;; FIXME: this is wrong, as not all subtypes of
173 ;; VECTOR are ARRAY-TYPEs [consider, for
174 ;; example, (OR (VECTOR T 3) (VECTOR T
175 ;; 4))]. However, it's difficult to see what we
176 ;; should put here... maybe we should
177 ;; GIVE-UP-IR1-TRANSFORM if the type is a
178 ;; subtype of VECTOR but not an ARRAY-TYPE?
179 bare))))))))
181 ;;; Return a DO loop, mapping a function FUN to elements of
182 ;;; sequences. SEQS is a list of lvars, SEQ-NAMES - list of variables,
183 ;;; bound to sequences, INTO - a variable, which is used in
184 ;;; MAP-INTO. RESULT and BODY are forms, which can use variables
185 ;;; FUNCALL-RESULT, containing the result of application of FUN, and
186 ;;; INDEX, containing the current position in sequences.
204 for seq-name in seq-names
245 :from-end t
247 body)))))
249 ;;; Try to compile %MAP efficiently when we can determine sequence
250 ;;; argument types at compile time.
253 "open code"
260 subtype-p
273 ;; The consing arity-1 cases can be implemented
274 ;; reasonably efficiently as function calls, and the cost
275 ;; of consing should be significantly larger than
276 ;; function call overhead, so we always compile these
277 ;; cases as full calls regardless of speed-versus-space
278 ;; optimization policy.
280 ;; (We use the same idiom, of returning a LAMBDA from
281 ;; DEFTRANSFORM, as is used in the DEFTRANSFORMs for
282 ;; FUNCALL and ALIEN-FUNCALL, and for the same
283 ;; reason: we need to get the runtime values of each
284 ;; of the &REST vars.)
309 all-seqs seq-args
310 :result result
311 :body push-dacc
317 ;;; MAP-INTO
321 "open code"
338 seqs seqs-names
344 funcall-result))
347 seqs seqs-names
353 result))
355 ;; %%vector-map-into-funs%% is not defined in xc
356 ;; if something needs to be faster in the compiler, it
357 ;; should declare the input sequences instead.
368 result))))
372 \f
373 ;;; FIXME: once the confusion over doing transforms with known-complex
374 ;;; arrays is over, we should also transform the calls to (AND (ARRAY
375 ;;; * (*)) (NOT (SIMPLE-ARRAY * (*)))) objects.
401 ;;; True if EQL comparisons involving type can be simplified to EQ.
407 ;; Write "%NAME-FUN1-FUN2-FUN3", etc. Not only is
408 ;; this ever so slightly faster then FORMAT, this
409 ;; way we are also proof against *PRINT-CASE*
410 ;; frobbing and such.
421 function-name key-functions variant)))
428 ;; If TEST is EQL, drop it.
431 ;; Ditto for KEY IDENTITY.
434 ;; Key can legally be NIL, but if it's NIL for sure we pretend it's
435 ;; not there at all. If it might be NIL, make up a form to that
436 ;; ensures it is a function.
480 key-form
490 ;; constant nil list
493 nil))
495 ;; specialized out-of-line version
500 ;; If KEY is IDENTITY, drop it.
503 ;; Key can legally be NIL, but if it's NIL for sure we pretend it's
504 ;; not there at all. If it might be NIL, make up a form to that
505 ;; ensures it is a function.
537 tail))
547 ;; constant nil list -- nothing to find!
548 nil)
550 ;; specialized out-of-line version
582 ',tail
584 nil)))
587 ;;; A similar transform used to apply to MEMBER and ASSOC, but since
588 ;;; TRANSFORM-LIST-ITEM-SEEK now takes care of them those transform
589 ;;; would never fire, and (%MEMBER-TEST ITEM LIST #'EQ) should be
590 ;;; almost as fast as MEMQ.
592 "convert to EQ test"
601 "open code"
624 "Unknown fill basher, please report to sbcl-devel: ~A"
625 basher-name)))
637 ;; BASH-VALUE is a word that we can repeatedly smash
638 ;; on the array: for less-than-word sized elements it
639 ;; contains multiple copies of the fill item.
648 (:tagged
650 (:char
652 (:bits
653 tmp)
654 (:single-float
657 (:double-float
661 (:complex-single-float
670 res))
679 (:tagged
681 (:char
683 (:bits
685 (:single-float
688 (:double-float
692 (:complex-single-float
699 collect
701 res))))))
706 *
719 ;; KLUDGE: WITH-ARRAY data in its full glory is going to mess up
720 ;; dynamic-extent for MAKE-ARRAY :INITIAL-ELEMENT initialization.
725 ;; Minor abuse CHECK-BOUND for bounds checking.
726 ;; (- END START) may still end up negative, but
727 ;; the basher handle that.
731 start)))
740 seq))
750 ;; WITH-ARRAY-DATA did our range checks once and for all, so
751 ;; it'd be wasteful to check again on every AREF...
752 ;; Force bounds-checks to 0 even if local policy had it >0.
758 data item start end)))
764 ;; ... though we still need to check that the new element can fit
765 ;; into the vector in safe code. -- CSR, 2002-07-05
775 :start start
777 \f
778 ;;;; hairy sequence transforms
780 ;;; FIXME: no hairy sequence transforms in SBCL?
781 ;;;
782 ;;; There used to be a bunch of commented out code about here,
783 ;;; containing the (apparent) beginning of hairy sequence transform
784 ;;; infrastructure. People interested in implementing better sequence
785 ;;; transforms might want to look at it for inspiration, even though
786 ;;; the actual code is ancient CMUCL -- and hence bitrotted. The code
787 ;;; was deleted in 1.0.7.23.
788 \f
789 ;;;; string operations
791 ;;; We transform the case-sensitive string predicates into a non-keyword
792 ;;; version. This is an IR1 transform so that we don't have to worry about
793 ;;; changing the order of evaluation.
797 * *)
806 ;;; Return a form that tests the free variables STRING1 and STRING2
807 ;;; for the ordering relationship specified by LESSP and EQUALP. The
808 ;;; start and end are also gotten from the environment. Both strings
809 ;;; must be SIMPLE-BASE-STRINGs.
816 string1 start1 end1 string2 start2 end2)))
826 (+ index
829 start1))))))
830 index)
873 `(,',result-fun
882 ;; An IF node doesn't care about the mismatch index.
883 ;; Transforming to (not (string= ..)) would lead to internal confusion
884 ;; due to incorrect typing: STRING/= can't return T, so return 0 for true.
890 \f
891 ;;;; transforms for sequence functions
893 ;;; FIXME: In the copy loops below, we code the loops in a strange
894 ;;; fashion:
895 ;;;
896 ;;; (do ((i (+ src-offset length) (1- i)))
897 ;;; ((<= i 0) ...)
898 ;;; (... (aref foo (1- i)) ...))
899 ;;;
900 ;;; rather than the more natural (and seemingly more efficient):
901 ;;;
902 ;;; (do ((i (1- (+ src-offset length)) (1- i)))
903 ;;; ((< i 0) ...)
904 ;;; (... (aref foo i) ...))
905 ;;;
906 ;;; (more efficient because we don't have to do the index adjusting on
907 ;;; every iteration of the loop)
908 ;;;
909 ;;; We do this to avoid a suboptimality in SBCL's backend. In the
910 ;;; latter case, the backend thinks I is a FIXNUM (which it is), but
911 ;;; when used as an array index, the backend thinks I is a
912 ;;; POSITIVE-FIXNUM (which it is). However, since the backend thinks of
913 ;;; these as distinct storage classes, it cannot coerce a move from a
914 ;;; FIXNUM TN to a POSITIVE-FIXNUM TN. The practical effect of this
915 ;;; deficiency is that we have two extra moves and increased register
916 ;;; pressure, which can lead to some spectacularly bad register
917 ;;; allocation. (sub-FIXME: the register allocation even with the
918 ;;; strangely written loops is not always excellent, either...). Doing
919 ;;; it the first way, above, means that I is always thought of as a
920 ;;; POSITIVE-FIXNUM and there are no issues.
921 ;;;
922 ;;; Besides, the *-WITH-OFFSET machinery will fold those index
923 ;;; adjustments in the first version into the array addressing at no
924 ;;; performance penalty!
926 ;;; This transform is critical to the performance of string streams. If
927 ;;; you tweak it, make sure that you compare the disassembly, if not the
928 ;;; performance of, the functions implementing string streams
929 ;;; (e.g. SB!IMPL::STRING-OUCH).
934 ,sequence-type1
951 n-element-bits)
954 seq1 start1 replace-len)))
957 ;; If the sequence types are different, SEQ1 and
958 ;; SEQ2 must be distinct arrays.
974 seq1))))
982 into forms
987 #!+sb-unicode
992 ;;; Expand simple cases of UB<SIZE>-BASH-COPY inline. "simple" is
993 ;;; defined as those cases where we are doing word-aligned copies from
994 ;;; both the source and the destination and we are copying from the same
995 ;;; offset from both the source and the destination. (The last
996 ;;; condition is there so we can determine the direction to copy at
997 ;;; compile time rather than runtime. Remember that UB<SIZE>-BASH-COPY
998 ;;; acts like memmove, not memcpy.) These conditions may seem rather
999 ;;; restrictive, but they do catch common cases, like allocating a (* 2
1000 ;;; N)-size buffer and blitting in the old N-size buffer in.
1003 dst dst-offset
1004 length n-elems-per-word)
1011 ;; Avoid non-word aligned copies.
1014 ;; Avoid copies where we would have to insert code for
1015 ;; determining the direction of copying.
1018 ;; FIXME: The cross-compiler doesn't optimize TRUNCATE properly,
1019 ;; so we have to do its work here.
1021 'length
1024 ;; Handle any bits at the end.
1027 ;; FIXME: The shift amount on this ASH is
1028 ;; *always* negative, but the backend doesn't
1029 ;; have a NEGATIVE-FIXNUM primitive type, so we
1030 ;; wind up with a pile of code that tests the
1031 ;; sign of the shift count prior to shifting when
1032 ;; all we need is a simple negate and shift
1033 ;; right. Yuck.
1051 ;; Copy from the end to save a register.
1058 #.
1062 index)
1063 *)))
1068 dst dst-offset length
1073 ;;; We expand copy loops inline in SUBSEQ and COPY-SEQ if we're copying
1074 ;;; arrays with elements of size >= the word size. We do this because
1075 ;;; we know the arrays cannot alias (one was just consed), therefore we
1076 ;;; can determine at compile time the direction to copy, and for
1077 ;;; word-sized elements, UB<WORD-SIZE>-BASH-COPY will do a bit of
1078 ;;; needless checking to figure out what's going on. The same
1079 ;;; considerations apply if we are copying elements larger than the word
1080 ;;; size, with the additional twist that doing it inline is likely to
1081 ;;; cons far less than calling REPLACE and letting generic code do the
1082 ;;; work.
1083 ;;;
1084 ;;; However, we do not do this for elements whose size is < than the
1085 ;;; word size because we don't want to deal with any alignment issues
1086 ;;; inline. The UB*-BASH-COPY transforms might fix things up later
1087 ;;; anyway.
1091 ;; The two transforms that use this test already specify that their
1092 ;; sequence argument is a VECTOR,
1093 ;; so this seems like it would be more efficient as
1094 ;; and (not (array-type-complexp type))
1095 ;; (not (eq (array-type-element-type type) *wild-type*))
1096 ;; Anyway it no longer works to write this as a single specifier
1097 ;; '(or (simple-unboxed-array (*)) simple-vector) because that
1098 ;; type is just (simple-array * (*)) which isn't amenable to
1099 ;; inline copying since we don't know what it holds.
1104 element-type)
1118 ;; KLUDGE: The compiler is not able to derive that (+ offset
1119 ;; length) must be a fixnum, but arrives at (unsigned-byte 29).
1120 ;; We, however, know it must be so, as by this point the bounds
1121 ;; have already been checked.
1129 ;;; MAKE-SEQUENCE, SUBSEQ, COPY-SEQ
1148 ;; Require sameness of dim and complexp. Give up on
1149 ;; (OR (VECTOR CHARACTER) (VECTOR BASE-CHAR 2))
1150 ;; which eventually fails in the call to the function.
1154 dim)
1161 types))
1162 dim complexp))))))
1168 ;; VECTOR means (VECTOR T)
1170 t
1174 ;; Don't transform if size is present in the specifier
1175 ;; and the SIZE argument is not known to be equal.
1178 ;; not sure what it would mean to make it non-simple
1183 ;; no transform, but we can detect some style issues
1192 ;; As with MAKE-ARRAY, this is merely undefined
1193 ;; behavior, not an error.
1195 "The default initial element ~S is not a ~S."
1196 default-initial-element elt-type))))
1197 ;; In would be possible in some cases,
1198 ;; like :INITIAL-ELEMENT (IF X #\x #\y) in a call
1199 ;; to MAKE-SEQUENCE '(VECTOR (MEMBER #\A #\B))
1200 ;; to detect erroneous non-constants initializers,
1201 ;; but it is not important enough to bother with.
1204 elt-ctype)))
1205 ;; MAKE-ARRAY considers this a warning, not an error.
1207 :initial-element
1209 elt-type)))))
1214 *
1233 result))))
1252 result)))
1261 \f
1263 key from-end)
1292 ;;; FIXME: it really should be possible to take advantage of the
1293 ;;; macros used in code/seq.lisp here to avoid duplication of code,
1294 ;;; and enable even funkier transformations.
1298 from-end)
1300 *
1301 :node node
1303 "open code"
1339 end2
1340 start2)))
1347 nil)
1348 ;; INDEX2 is FIXNUM, not an INDEX, as right before the loop
1349 ;; terminates is hits -1 when :FROM-END is true and :START2
1350 ;; is 0.
1368 elt)))
1375 elt)))
1381 &key start1 end1 start2 end2
1396 max-result))
1401 constant-end1)
1407 ;; The result can be equal to MAX-RESULT only when
1408 ;; searching for "" and :start2 being equal to :end2
1412 0
1415 min1))))
1418 null))))
1430 max-result)))
1432 max-result
1436 &key start1 end1
1439 ;; Could be as smart as the SEARCH one above but I ran out of steam.
1444 &key start end
1452 &key start end
1460 &key start end
1468 &key start end
1476 &key start end
1484 &key start end
1503 ~/sb!impl:print-type/"
1504 constant-start constant-end sequence-type))))
1507 ;; Would be a good idea to transform to something like
1508 ;; %compile-time-type-error
1519 null-type)
1521 list-type)))
1523 list-type)
1525 null-type)
1530 ;; Can't trust lengths from non-simple vectors due to
1531 ;; fill-pointer and adjust-array
1541 constant-start)
1555 simplified))))
1557 nil)
1563 ;;; Open-code CONCATENATE for strings. It would be possible to extend
1564 ;;; this transform to non-strings, but I chose to just do the case that
1565 ;;; should cover 95% of CONCATENATE performance complaints for now.
1566 ;;; -- JES, 2007-11-17
1567 ;;;
1568 ;;; Only handle the simple result type cases. If somebody does (CONCATENATE
1569 ;;; '(STRING 6) ...) their code won't be optimized, but nobody does that in
1570 ;;; practice.
1571 ;;;
1572 ;;; Limit full open coding based on length of constant sequences. Default
1573 ;;; value is chosen so that other parts of the compiler (constraint propagation
1574 ;;; mainly) won't go nonlinear too badly. It's not an exact number -- but
1575 ;;; in the right ballpark.
1581 ;; Out-of-line
1583 ;; Strings are handled more efficiently by
1584 ;; %concatenate-to-* functions
1586 for lvar in lvars
1590 var))))
1599 ;; Inline
1608 for var in vars
1612 sequence)
1613 ,var
1614 #-sb-xc-host
1633 for value in lvar-values
1634 for var in vars
1635 collect
1638 ;; Fold the array reads for constant arguments
1641 for i from 0
1642 collect
1643 ;; Without truly-the we get massive numbers
1644 ;; of pointless error traps.
1655 (#!+sb-unicode
1658 t)
1659 ,var
1667 .string.))))))
1670 ;; FIXME: This only accepts vectors without dimensions even though
1671 ;; it's not that hard to support them for the concatenate transform,
1672 ;; but it's probably not used often enough to bother.
1678 el-ctype))
1686 #!+sb-unicode
1688 #!-sb-unicode
1698 ;; Lists are faster to iterate over than vectors of
1699 ;; unknown type.
1701 for lvar in lvars
1704 var))))
1716 #!+sb-unicode
1719 ;; FIXME: other vectors may use inlined expansion from
1720 ;; STRING-CONCATENATE-TRANSFORM as well.
1727 `(%concatenate-to-simple-vector
1729 `(%concatenate-to-vector
1731 \f
1732 ;;;; CONS accessor DERIVE-TYPE optimizers
1735 ;; This and CDR needs to use LVAR-CONSERVATIVE-TYPE because type inference
1736 ;; gets confused by things like (SETF CAR).
1740 null-type)
1748 null-type)
1751 \f
1752 ;;;; FIND, POSITION, and their -IF and -IF-NOT variants
1755 start end from-end))
1758 ;; If :KEY is a known function, then regardless of the :TEST,
1759 ;; FIND returns an object of the type that KEY accepts, or nil.
1760 ;; If LVAR-FUN-NAME can't be determined, it returns NIL.
1761 ;; :KEY NIL is valid, and means #'IDENTITY.
1762 ;; So either way, we get IDENTITY which skips this code.
1772 ;; Otherwise maybe FIND returns ITEM itself (or an EQL number).
1773 ;; :TEST is allowed only if EQ or EQL (where NIL means EQL).
1774 ;; :KEY is allowed only if IDENTITY or NIL.
1784 ;;; We want to make sure that %FIND-POSITION is inline-expanded into
1785 ;;; %FIND-POSITION-IF only when %FIND-POSITION-IF has an inline
1786 ;;; expansion, so we factor out the condition into this function.
1790 ;; It's not worth trying to inline vector code unless we
1791 ;; know a fair amount about it at compile time.
1797 ;; Inlining on lists is generally worthwhile.
1798 )
1803 ;;; %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for LIST data
1806 ;; Circularity detection slows things down. It is permissible not to.
1807 ;; In fact, FIND is given as an archetypal example of a function that
1808 ;; "should be prepared to signal an error" but might not [CLHS 1.4.2].
1809 ;; We relax the definition of "safe" from safety=3 to >=2.
1811 ;; The secondary value is inconsequential when flowing into a non-MV
1812 ;; combination, so we avoid counting loop iterations if possible.
1813 ;; This is limited in power, but good enough, for want of a proper
1814 ;; dead-code-elimination phase of the compiler.
1843 ;; If you have as many as INDEX conses on a 32-bit build,
1844 ;; then you've either used up 4GB of memory (impossible)
1845 ;; or you're stuck in a circular list in unsafe code.
1846 ;; Correspondingly larger limit for 64-bit.
1850 ;; This hack of dealing with non-NIL FROM-END for list data
1851 ;; by iterating forward through the list and keeping track of
1852 ;; the last time we found a match might be more screwy than
1853 ;; what the user expects, but it seems to be allowed by the
1854 ;; ANSI standard. (And if the user is screwy enough to ask
1855 ;; for FROM-END behavior on list data, turnabout is fair play.)
1856 ;;
1857 ;; It's also not enormously efficient, calling PREDICATE
1858 ;; and KEY more often than necessary; but all the alternatives
1859 ;; seem to have their own efficiency problems.
1868 *
1869 :node node
1871 "expand inline"
1873 from-end start end node))))
1877 ;;; %FIND-POSITION for LIST data can be expanded into %FIND-POSITION-IF
1878 ;;; without loss of efficiency. (I.e., the optimizer should be able
1879 ;;; to straighten everything out.)
1882 *
1884 "expand inline"
1886 ;; The order of arguments for asymmetric tests
1887 ;; (e.g. #'<, as opposed to order-independent
1888 ;; tests like #'=) is specified in the spec
1889 ;; section 17.2.1 -- the O/Zi stuff there.
1892 sequence
1893 from-end
1894 start
1895 end
1898 ;;; The inline expansions for the VECTOR case are saved as macros so
1899 ;;; that we can share them between the DEFTRANSFORMs and the default
1900 ;;; cases in the DEFUNs. (This isn't needed for the LIST case, because
1901 ;;; the DEFTRANSFORMs for LIST are less choosy about when to expand.)
1903 from-end
1904 start
1905 end-arg
1906 element
1907 done-p-expr)
1916 ;; WITH-ARRAY-DATA has already performed bounds
1917 ;; checking, so we can safely elide the checks
1918 ;; in the inner loop.
1927 ;; (If we aren't fastidious about declaring that
1928 ;; INDEX might be -1, then (FIND 1 #() :FROM-END T)
1929 ;; can send us off into never-never land, since
1930 ;; INDEX is initialized to -1.)
1931 of-type index-or-minus-1
1939 from-end start end key test)
1941 (%find-position-or-find-position-if-vector-expansion
1942 sequence
1943 from-end
1944 start
1945 end
1946 element
1947 ;; (See the LIST transform for a discussion of the correct
1948 ;; argument order, i.e. whether the searched-for ,ITEM goes before
1949 ;; or after the checked sequence element.)
1953 from-end start end key)
1955 (%find-position-or-find-position-if-vector-expansion
1956 sequence
1957 from-end
1958 start
1959 end
1960 element
1964 from-end start end key)
1966 (%find-position-or-find-position-if-vector-expansion
1967 sequence
1968 from-end
1969 start
1970 end
1971 element
1974 ;;; %FIND-POSITION, %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for
1975 ;;; VECTOR data
1978 *
1980 "expand inline"
1982 '(%find-position-if-vector-macro predicate sequence
1983 from-end start end key))
1987 *
1989 "expand inline"
1991 '(%find-position-if-not-vector-macro predicate sequence
1992 from-end start end key))
1996 *
1998 "expand inline"
2000 '(%find-position-vector-macro item sequence
2001 from-end start end key test))
2030 *
2037 sequence
2040 form
2041 ;; Otherwise we'd get three instances of WITH-ARRAY-DATA from
2042 ;; %FIND-POSITION.
2049 ;; The type is known exactly, other transforms will take care of it.
2052 ;;; logic to unravel :TEST, :TEST-NOT, and :KEY options in FIND,
2053 ;;; POSITION-IF, etc.
2061 (,test-not
2062 ;; (Without DYNAMIC-EXTENT, this is potentially horribly
2063 ;; inefficient, but since the TEST-NOT option is deprecated
2064 ;; anyway, we don't care.)
2066 ;; :TEST of NIL (whether implicit or explicit) means #'EQL.
2067 ;; This behavior is not specified by CLHS, but is fairly conventional.
2068 ;; (KEY is expressly specified as allowing NIL, but TEST is not)
2069 ;; In our implementation, it has to be this way because we don't track
2070 ;; whether the :TEST and :TEST-NOT args were actually present.
2081 key test test-not)
2084 (%find-position item sequence
2085 from-end start
2086 end
2089 test test-not))))))
2096 end key)
2099 ,values-index
2101 sequence from-end
2102 start end
2107 ;;; the deprecated functions FIND-IF-NOT and POSITION-IF-NOT. We
2108 ;;; didn't bother to worry about optimizing them, except note that on
2109 ;;; Sat, Oct 06, 2001 at 04:22:38PM +0100, Christophe Rhodes wrote on
2110 ;;; sbcl-devel
2111 ;;;
2112 ;;; My understanding is that while the :test-not argument is
2113 ;;; deprecated in favour of :test (complement #'foo) because of
2114 ;;; semantic difficulties (what happens if both :test and :test-not
2115 ;;; are supplied, etc) the -if-not variants, while officially
2116 ;;; deprecated, would be undeprecated were X3J13 actually to produce
2117 ;;; a revised standard, as there are perfectly legitimate idiomatic
2118 ;;; reasons for allowing the -if-not versions equal status,
2119 ;;; particularly remove-if-not (== filter).
2120 ;;;
2121 ;;; This is only an informal understanding, I grant you, but
2122 ;;; perhaps it's worth optimizing the -if-not versions in the same
2123 ;;; way as the others?
2124 ;;;
2125 ;;; FIXME: Maybe remove uses of these deprecated functions within the
2126 ;;; implementation of SBCL.
2130 end key)
2133 ,values-index
2135 sequence from-end
2136 start end
2146 ;; If the bag is constant, use MEMBER
2147 ;; instead of FIND, since we have a
2148 ;; deftransform for MEMBER that can
2149 ;; open-code all of the comparisons when
2150 ;; the list is constant. -- JES, 2007-12-10
2162 index)
2171 end)))
2174 string
2180 \f
2181 ;;; (partially) constant-fold backq-* functions, or convert to their
2182 ;;; plain CL equivalent (now that they're not needed for pprinting).
2184 ;; Pop constant values from the end, list/list* them if any, and link
2185 ;; the remainder with list* at runtime.
2193 constants))
2199 `',tail
2214 ;; Merge adjacent constant values
2230 "Non-list or improper list spliced in ~
2242 \f
2254 \f
2260 nil)
2290 cons-type
2298 cons-type
2305 nil)
2313 nil)
2319 t)
2325 t)
2344 \f
2350 t)