| blob | 8fed4ce34c8dd6ce4955e5d7cf88b5192e4caa65 |
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"
261 subtype-p
275 ;; The consing arity-1 cases can be implemented
276 ;; reasonably efficiently as function calls, and the cost
277 ;; of consing should be significantly larger than
278 ;; function call overhead, so we always compile these
279 ;; cases as full calls regardless of speed-versus-space
280 ;; optimization policy.
282 ;; (We use the same idiom, of returning a LAMBDA from
283 ;; DEFTRANSFORM, as is used in the DEFTRANSFORMs for
284 ;; FUNCALL and ALIEN-FUNCALL, and for the same
285 ;; reason: we need to get the runtime values of each
286 ;; of the &REST vars.)
311 all-seqs seq-args
312 :result result
313 :body push-dacc
319 ;;; MAP-INTO
323 "open code"
340 seqs seqs-names
346 funcall-result))
349 seqs seqs-names
355 result))
357 ;; %%vector-map-into-funs%% is not defined in xc
358 ;; if something needs to be faster in the compiler, it
359 ;; should declare the input sequences instead.
371 result))))
375 \f
376 ;;; FIXME: once the confusion over doing transforms with known-complex
377 ;;; arrays is over, we should also transform the calls to (AND (ARRAY
378 ;;; * (*)) (NOT (SIMPLE-ARRAY * (*)))) objects.
404 ;;; True if EQL comparisons involving type can be simplified to EQ.
410 ;; Write "%NAME-FUN1-FUN2-FUN3", etc. Not only is
411 ;; this ever so slightly faster then FORMAT, this
412 ;; way we are also proof against *PRINT-CASE*
413 ;; frobbing and such.
424 function-name key-functions variant)))
431 ;; If TEST is EQL, drop it.
434 ;; Ditto for KEY IDENTITY.
437 ;; Key can legally be NIL, but if it's NIL for sure we pretend it's
438 ;; not there at all. If it might be NIL, make up a form to that
439 ;; ensures it is a function.
483 key-form
493 ;; constant nil list
496 nil))
498 ;; specialized out-of-line version
503 ;; If KEY is IDENTITY, drop it.
506 ;; Key can legally be NIL, but if it's NIL for sure we pretend it's
507 ;; not there at all. If it might be NIL, make up a form to that
508 ;; ensures it is a function.
540 tail))
550 ;; constant nil list -- nothing to find!
551 nil)
553 ;; specialized out-of-line version
585 ',tail
587 nil)))
590 ;;; A similar transform used to apply to MEMBER and ASSOC, but since
591 ;;; TRANSFORM-LIST-ITEM-SEEK now takes care of them those transform
592 ;;; would never fire, and (%MEMBER-TEST ITEM LIST #'EQ) should be
593 ;;; almost as fast as MEMQ.
595 "convert to EQ test"
604 "open code"
627 "Unknown fill basher, please report to sbcl-devel: ~A"
628 basher-name)))
640 ;; BASH-VALUE is a word that we can repeatedly smash
641 ;; on the array: for less-than-word sized elements it
642 ;; contains multiple copies of the fill item.
651 (:tagged
653 (:char
655 (:bits
656 tmp)
657 (:single-float
660 (:double-float
664 (:complex-single-float
673 res))
682 (:tagged
684 (:char
686 (:bits
688 (:single-float
691 (:double-float
695 (:complex-single-float
702 collect
704 res))))))
709 *
722 ;; KLUDGE: WITH-ARRAY data in its full glory is going to mess up
723 ;; dynamic-extent for MAKE-ARRAY :INITIAL-ELEMENT initialization.
728 ;; Minor abuse CHECK-BOUND for bounds checking.
729 ;; (- END START) may still end up negative, but
730 ;; the basher handle that.
734 start)))
743 seq))
753 ;; WITH-ARRAY-DATA did our range checks once and for all, so
754 ;; it'd be wasteful to check again on every AREF...
755 ;; Force bounds-checks to 0 even if local policy had it >0.
761 data item start end))
767 seq)
768 ;; ... though we still need to check that the new element can fit
769 ;; into the vector in safe code. -- CSR, 2002-07-05
779 :start start
781 \f
782 ;;;; hairy sequence transforms
784 ;;; FIXME: no hairy sequence transforms in SBCL?
785 ;;;
786 ;;; There used to be a bunch of commented out code about here,
787 ;;; containing the (apparent) beginning of hairy sequence transform
788 ;;; infrastructure. People interested in implementing better sequence
789 ;;; transforms might want to look at it for inspiration, even though
790 ;;; the actual code is ancient CMUCL -- and hence bitrotted. The code
791 ;;; was deleted in 1.0.7.23.
792 \f
793 ;;;; string operations
795 ;;; We transform the case-sensitive string predicates into a non-keyword
796 ;;; version. This is an IR1 transform so that we don't have to worry about
797 ;;; changing the order of evaluation.
801 * *)
810 ;;; Return a form that tests the free variables STRING1 and STRING2
811 ;;; for the ordering relationship specified by LESSP and EQUALP. The
812 ;;; start and end are also gotten from the environment. Both strings
813 ;;; must be SIMPLE-BASE-STRINGs.
820 string1 start1 end1 string2 start2 end2)))
830 (+ index
833 start1))))))
834 index)
877 `(,',result-fun
886 ;; An IF node doesn't care about the mismatch index.
887 ;; Transforming to (not (string= ..)) would lead to internal confusion
888 ;; due to incorrect typing: STRING/= can't return T, so return 0 for true.
895 \f
896 ;;;; transforms for sequence functions
898 ;;; FIXME: In the copy loops below, we code the loops in a strange
899 ;;; fashion:
900 ;;;
901 ;;; (do ((i (+ src-offset length) (1- i)))
902 ;;; ((<= i 0) ...)
903 ;;; (... (aref foo (1- i)) ...))
904 ;;;
905 ;;; rather than the more natural (and seemingly more efficient):
906 ;;;
907 ;;; (do ((i (1- (+ src-offset length)) (1- i)))
908 ;;; ((< i 0) ...)
909 ;;; (... (aref foo i) ...))
910 ;;;
911 ;;; (more efficient because we don't have to do the index adjusting on
912 ;;; every iteration of the loop)
913 ;;;
914 ;;; We do this to avoid a suboptimality in SBCL's backend. In the
915 ;;; latter case, the backend thinks I is a FIXNUM (which it is), but
916 ;;; when used as an array index, the backend thinks I is a
917 ;;; POSITIVE-FIXNUM (which it is). However, since the backend thinks of
918 ;;; these as distinct storage classes, it cannot coerce a move from a
919 ;;; FIXNUM TN to a POSITIVE-FIXNUM TN. The practical effect of this
920 ;;; deficiency is that we have two extra moves and increased register
921 ;;; pressure, which can lead to some spectacularly bad register
922 ;;; allocation. (sub-FIXME: the register allocation even with the
923 ;;; strangely written loops is not always excellent, either...). Doing
924 ;;; it the first way, above, means that I is always thought of as a
925 ;;; POSITIVE-FIXNUM and there are no issues.
926 ;;;
927 ;;; Besides, the *-WITH-OFFSET machinery will fold those index
928 ;;; adjustments in the first version into the array addressing at no
929 ;;; performance penalty!
931 ;;; This transform is critical to the performance of string streams. If
932 ;;; you tweak it, make sure that you compare the disassembly, if not the
933 ;;; performance of, the functions implementing string streams
934 ;;; (e.g. SB!IMPL::STRING-OUCH).
939 ,sequence-type1
956 n-element-bits)
959 seq1 start1 replace-len)))
962 ;; If the sequence types are different, SEQ1 and
963 ;; SEQ2 must be distinct arrays.
979 seq1))))
987 into forms
992 #!+sb-unicode
997 ;;; Expand simple cases of UB<SIZE>-BASH-COPY inline. "simple" is
998 ;;; defined as those cases where we are doing word-aligned copies from
999 ;;; both the source and the destination and we are copying from the same
1000 ;;; offset from both the source and the destination. (The last
1001 ;;; condition is there so we can determine the direction to copy at
1002 ;;; compile time rather than runtime. Remember that UB<SIZE>-BASH-COPY
1003 ;;; acts like memmove, not memcpy.) These conditions may seem rather
1004 ;;; restrictive, but they do catch common cases, like allocating a (* 2
1005 ;;; N)-size buffer and blitting in the old N-size buffer in.
1008 dst dst-offset
1009 length n-elems-per-word)
1016 ;; Avoid non-word aligned copies.
1019 ;; Avoid copies where we would have to insert code for
1020 ;; determining the direction of copying.
1023 ;; FIXME: The cross-compiler doesn't optimize TRUNCATE properly,
1024 ;; so we have to do its work here.
1026 'length
1029 ;; Handle any bits at the end.
1032 ;; FIXME: The shift amount on this ASH is
1033 ;; *always* negative, but the backend doesn't
1034 ;; have a NEGATIVE-FIXNUM primitive type, so we
1035 ;; wind up with a pile of code that tests the
1036 ;; sign of the shift count prior to shifting when
1037 ;; all we need is a simple negate and shift
1038 ;; right. Yuck.
1056 ;; Copy from the end to save a register.
1063 #.
1067 index)
1068 *)))
1073 dst dst-offset length
1078 ;;; We expand copy loops inline in SUBSEQ and COPY-SEQ if we're copying
1079 ;;; arrays with elements of size >= the word size. We do this because
1080 ;;; we know the arrays cannot alias (one was just consed), therefore we
1081 ;;; can determine at compile time the direction to copy, and for
1082 ;;; word-sized elements, UB<WORD-SIZE>-BASH-COPY will do a bit of
1083 ;;; needless checking to figure out what's going on. The same
1084 ;;; considerations apply if we are copying elements larger than the word
1085 ;;; size, with the additional twist that doing it inline is likely to
1086 ;;; cons far less than calling REPLACE and letting generic code do the
1087 ;;; work.
1088 ;;;
1089 ;;; However, we do not do this for elements whose size is < than the
1090 ;;; word size because we don't want to deal with any alignment issues
1091 ;;; inline. The UB*-BASH-COPY transforms might fix things up later
1092 ;;; anyway.
1096 ;; The two transforms that use this test already specify that their
1097 ;; sequence argument is a VECTOR,
1098 ;; so this seems like it would be more efficient as
1099 ;; and (not (array-type-complexp type))
1100 ;; (not (eq (array-type-element-type type) *wild-type*))
1101 ;; Anyway it no longer works to write this as a single specifier
1102 ;; '(or (simple-unboxed-array (*)) simple-vector) because that
1103 ;; type is just (simple-array * (*)) which isn't amenable to
1104 ;; inline copying since we don't know what it holds.
1109 element-type)
1123 ;; KLUDGE: The compiler is not able to derive that (+ offset
1124 ;; length) must be a fixnum, but arrives at (unsigned-byte 29).
1125 ;; We, however, know it must be so, as by this point the bounds
1126 ;; have already been checked.
1134 ;;; MAKE-SEQUENCE, SUBSEQ, COPY-SEQ
1153 ;; Require sameness of dim and complexp. Give up on
1154 ;; (OR (VECTOR CHARACTER) (VECTOR BASE-CHAR 2))
1155 ;; which eventually fails in the call to the function.
1159 dim)
1166 types))
1167 dim complexp))))))
1173 ;; VECTOR means (VECTOR T)
1175 t
1179 ;; Don't transform if size is present in the specifier
1180 ;; and the SIZE argument is not known to be equal.
1183 ;; not sure what it would mean to make it non-simple
1188 ;; no transform, but we can detect some style issues
1197 ;; As with MAKE-ARRAY, this is merely undefined
1198 ;; behavior, not an error.
1200 "The default initial element ~S is not a ~S."
1201 default-initial-element elt-type))))
1202 ;; In would be possible in some cases,
1203 ;; like :INITIAL-ELEMENT (IF X #\x #\y) in a call
1204 ;; to MAKE-SEQUENCE '(VECTOR (MEMBER #\A #\B))
1205 ;; to detect erroneous non-constants initializers,
1206 ;; but it is not important enough to bother with.
1209 elt-ctype)))
1210 ;; MAKE-ARRAY considers this a warning, not an error.
1212 :initial-element
1214 elt-type)))))
1219 *
1238 result))))
1257 result)))
1266 \f
1268 key from-end)
1297 ;;; FIXME: it really should be possible to take advantage of the
1298 ;;; macros used in code/seq.lisp here to avoid duplication of code,
1299 ;;; and enable even funkier transformations.
1303 from-end)
1305 *
1306 :node node
1308 "open code"
1344 end2
1345 start2)))
1352 nil)
1353 ;; INDEX2 is FIXNUM, not an INDEX, as right before the loop
1354 ;; terminates is hits -1 when :FROM-END is true and :START2
1355 ;; is 0.
1373 elt)))
1380 elt)))
1386 &key start1 end1 start2 end2
1401 max-result))
1406 constant-end1)
1412 ;; The result can be equal to MAX-RESULT only when
1413 ;; searching for "" and :start2 being equal to :end2
1417 0
1420 min1))))
1423 null))))
1435 max-result)))
1437 max-result
1441 &key start1 end1
1444 ;; Could be as smart as the SEARCH one above but I ran out of steam.
1449 &key start end
1457 &key start end
1465 &key start end
1473 &key start end
1481 &key start end
1489 &key start end
1508 ~/sb!impl:print-type/"
1509 constant-start constant-end sequence-type))))
1512 ;; Would be a good idea to transform to something like
1513 ;; %compile-time-type-error
1524 null-type)
1526 list-type)))
1528 list-type)
1530 null-type)
1535 ;; Can't trust lengths from non-simple vectors due to
1536 ;; fill-pointer and adjust-array
1546 constant-start)
1560 simplified))))
1562 nil)
1568 ;;; Open-code CONCATENATE for strings. It would be possible to extend
1569 ;;; this transform to non-strings, but I chose to just do the case that
1570 ;;; should cover 95% of CONCATENATE performance complaints for now.
1571 ;;; -- JES, 2007-11-17
1572 ;;;
1573 ;;; Only handle the simple result type cases. If somebody does (CONCATENATE
1574 ;;; '(STRING 6) ...) their code won't be optimized, but nobody does that in
1575 ;;; practice.
1576 ;;;
1577 ;;; Limit full open coding based on length of constant sequences. Default
1578 ;;; value is chosen so that other parts of the compiler (constraint propagation
1579 ;;; mainly) won't go nonlinear too badly. It's not an exact number -- but
1580 ;;; in the right ballpark.
1586 ;; Out-of-line
1588 ;; Strings are handled more efficiently by
1589 ;; %concatenate-to-* functions
1591 for lvar in lvars
1595 var))))
1604 ;; Inline
1613 for var in vars
1617 sequence)
1618 ,var
1619 #-sb-xc-host
1638 for value in lvar-values
1639 for var in vars
1640 collect
1643 ;; Fold the array reads for constant arguments
1646 for i from 0
1647 collect
1648 ;; Without truly-the we get massive numbers
1649 ;; of pointless error traps.
1660 (#!+sb-unicode
1663 t)
1664 ,var
1672 .string.))))))
1675 ;; FIXME: This only accepts vectors without dimensions even though
1676 ;; it's not that hard to support them for the concatenate transform,
1677 ;; but it's probably not used often enough to bother.
1683 el-ctype))
1692 #!+sb-unicode
1694 #!-sb-unicode
1704 ;; Lists are faster to iterate over than vectors of
1705 ;; unknown type.
1707 for lvar in lvars
1710 var))))
1722 #!+sb-unicode
1725 ;; FIXME: other vectors may use inlined expansion from
1726 ;; STRING-CONCATENATE-TRANSFORM as well.
1733 `(%concatenate-to-simple-vector
1735 `(%concatenate-to-vector
1737 \f
1738 ;;;; CONS accessor DERIVE-TYPE optimizers
1741 ;; This and CDR needs to use LVAR-CONSERVATIVE-TYPE because type inference
1742 ;; gets confused by things like (SETF CAR).
1746 null-type)
1754 null-type)
1757 \f
1758 ;;;; FIND, POSITION, and their -IF and -IF-NOT variants
1761 start end from-end))
1764 ;; If :KEY is a known function, then regardless of the :TEST,
1765 ;; FIND returns an object of the type that KEY accepts, or nil.
1766 ;; If LVAR-FUN-NAME can't be determined, it returns NIL.
1767 ;; :KEY NIL is valid, and means #'IDENTITY.
1768 ;; So either way, we get IDENTITY which skips this code.
1779 ;; Otherwise maybe FIND returns ITEM itself (or an EQL number).
1780 ;; :TEST is allowed only if EQ or EQL (where NIL means EQL).
1781 ;; :KEY is allowed only if IDENTITY or NIL.
1790 ;;; We want to make sure that %FIND-POSITION is inline-expanded into
1791 ;;; %FIND-POSITION-IF only when %FIND-POSITION-IF has an inline
1792 ;;; expansion, so we factor out the condition into this function.
1796 ;; It's not worth trying to inline vector code unless we
1797 ;; know a fair amount about it at compile time.
1803 ;; Inlining on lists is generally worthwhile.
1804 )
1809 ;;; %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for LIST data
1812 ;; Circularity detection slows things down. It is permissible not to.
1813 ;; In fact, FIND is given as an archetypal example of a function that
1814 ;; "should be prepared to signal an error" but might not [CLHS 1.4.2].
1815 ;; We relax the definition of "safe" from safety=3 to >=2.
1817 ;; The secondary value is inconsequential when flowing into a non-MV
1818 ;; combination, so we avoid counting loop iterations if possible.
1819 ;; This is limited in power, but good enough, for want of a proper
1820 ;; dead-code-elimination phase of the compiler.
1849 ;; If you have as many as INDEX conses on a 32-bit build,
1850 ;; then you've either used up 4GB of memory (impossible)
1851 ;; or you're stuck in a circular list in unsafe code.
1852 ;; Correspondingly larger limit for 64-bit.
1856 ;; This hack of dealing with non-NIL FROM-END for list data
1857 ;; by iterating forward through the list and keeping track of
1858 ;; the last time we found a match might be more screwy than
1859 ;; what the user expects, but it seems to be allowed by the
1860 ;; ANSI standard. (And if the user is screwy enough to ask
1861 ;; for FROM-END behavior on list data, turnabout is fair play.)
1862 ;;
1863 ;; It's also not enormously efficient, calling PREDICATE
1864 ;; and KEY more often than necessary; but all the alternatives
1865 ;; seem to have their own efficiency problems.
1874 *
1875 :node node
1877 "expand inline"
1879 from-end start end node))))
1883 ;;; %FIND-POSITION for LIST data can be expanded into %FIND-POSITION-IF
1884 ;;; without loss of efficiency. (I.e., the optimizer should be able
1885 ;;; to straighten everything out.)
1888 *
1890 "expand inline"
1892 ;; The order of arguments for asymmetric tests
1893 ;; (e.g. #'<, as opposed to order-independent
1894 ;; tests like #'=) is specified in the spec
1895 ;; section 17.2.1 -- the O/Zi stuff there.
1898 sequence
1899 from-end
1900 start
1901 end
1904 ;;; The inline expansions for the VECTOR case are saved as macros so
1905 ;;; that we can share them between the DEFTRANSFORMs and the default
1906 ;;; cases in the DEFUNs. (This isn't needed for the LIST case, because
1907 ;;; the DEFTRANSFORMs for LIST are less choosy about when to expand.)
1909 from-end
1910 start
1911 end-arg
1912 element
1913 done-p-expr)
1922 ;; WITH-ARRAY-DATA has already performed bounds
1923 ;; checking, so we can safely elide the checks
1924 ;; in the inner loop.
1933 ;; (If we aren't fastidious about declaring that
1934 ;; INDEX might be -1, then (FIND 1 #() :FROM-END T)
1935 ;; can send us off into never-never land, since
1936 ;; INDEX is initialized to -1.)
1937 of-type index-or-minus-1
1945 from-end start end key test)
1947 (%find-position-or-find-position-if-vector-expansion
1948 sequence
1949 from-end
1950 start
1951 end
1952 element
1953 ;; (See the LIST transform for a discussion of the correct
1954 ;; argument order, i.e. whether the searched-for ,ITEM goes before
1955 ;; or after the checked sequence element.)
1959 from-end start end key)
1961 (%find-position-or-find-position-if-vector-expansion
1962 sequence
1963 from-end
1964 start
1965 end
1966 element
1970 from-end start end key)
1972 (%find-position-or-find-position-if-vector-expansion
1973 sequence
1974 from-end
1975 start
1976 end
1977 element
1980 ;;; %FIND-POSITION, %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for
1981 ;;; VECTOR data
1984 *
1986 "expand inline"
1988 '(%find-position-if-vector-macro predicate sequence
1989 from-end start end key))
1993 *
1995 "expand inline"
1997 '(%find-position-if-not-vector-macro predicate sequence
1998 from-end start end key))
2002 *
2004 "expand inline"
2006 '(%find-position-vector-macro item sequence
2007 from-end start end key test))
2036 *
2043 sequence
2046 form
2047 ;; Otherwise we'd get three instances of WITH-ARRAY-DATA from
2048 ;; %FIND-POSITION.
2055 ;; The type is known exactly, other transforms will take care of it.
2058 ;;; logic to unravel :TEST, :TEST-NOT, and :KEY options in FIND,
2059 ;;; POSITION-IF, etc.
2067 (,test-not
2068 ;; (Without DYNAMIC-EXTENT, this is potentially horribly
2069 ;; inefficient, but since the TEST-NOT option is deprecated
2070 ;; anyway, we don't care.)
2072 ;; :TEST of NIL (whether implicit or explicit) means #'EQL.
2073 ;; This behavior is not specified by CLHS, but is fairly conventional.
2074 ;; (KEY is expressly specified as allowing NIL, but TEST is not)
2075 ;; In our implementation, it has to be this way because we don't track
2076 ;; whether the :TEST and :TEST-NOT args were actually present.
2087 key test test-not)
2090 (%find-position item sequence
2091 from-end start
2092 end
2095 test test-not))))))
2102 end key)
2105 ,values-index
2107 sequence from-end
2108 start end
2113 ;;; the deprecated functions FIND-IF-NOT and POSITION-IF-NOT. We
2114 ;;; didn't bother to worry about optimizing them, except note that on
2115 ;;; Sat, Oct 06, 2001 at 04:22:38PM +0100, Christophe Rhodes wrote on
2116 ;;; sbcl-devel
2117 ;;;
2118 ;;; My understanding is that while the :test-not argument is
2119 ;;; deprecated in favour of :test (complement #'foo) because of
2120 ;;; semantic difficulties (what happens if both :test and :test-not
2121 ;;; are supplied, etc) the -if-not variants, while officially
2122 ;;; deprecated, would be undeprecated were X3J13 actually to produce
2123 ;;; a revised standard, as there are perfectly legitimate idiomatic
2124 ;;; reasons for allowing the -if-not versions equal status,
2125 ;;; particularly remove-if-not (== filter).
2126 ;;;
2127 ;;; This is only an informal understanding, I grant you, but
2128 ;;; perhaps it's worth optimizing the -if-not versions in the same
2129 ;;; way as the others?
2130 ;;;
2131 ;;; FIXME: Maybe remove uses of these deprecated functions within the
2132 ;;; implementation of SBCL.
2136 end key)
2139 ,values-index
2141 sequence from-end
2142 start end
2152 ;; If the bag is constant, use MEMBER
2153 ;; instead of FIND, since we have a
2154 ;; deftransform for MEMBER that can
2155 ;; open-code all of the comparisons when
2156 ;; the list is constant. -- JES, 2007-12-10
2168 index)
2177 end)))
2180 string
2186 \f
2187 ;;; (partially) constant-fold backq-* functions, or convert to their
2188 ;;; plain CL equivalent (now that they're not needed for pprinting).
2190 ;; Pop constant values from the end, list/list* them if any, and link
2191 ;; the remainder with list* at runtime.
2199 constants))
2205 `',tail
2220 ;; Merge adjacent constant values
2236 "Non-list or improper list spliced in ~
2248 \f
2260 \f
2266 nil)
2296 cons-type
2304 cons-type
2311 nil)
2319 nil)
2325 t)
2331 t)
2350 \f
2356 t)