;;;; functions to implement arrays ;;;; This software is part of the SBCL system. See the README file for ;;;; more information. ;;;; ;;;; This software is derived from the CMU CL system, which was ;;;; written at Carnegie Mellon University and released into the ;;;; public domain. The software is in the public domain and is ;;;; provided with absolutely no warranty. See the COPYING and CREDITS ;;;; files for more information. (in-package "SB!IMPL") #!-sb-fluid (declaim (inline adjustable-array-p array-displacement)) ;;;; miscellaneous accessor functions ;;; These functions are only needed by the interpreter, 'cause the ;;; compiler inlines them. (macrolet ((def (name) `(progn (defun ,name (array) (,name array)) (defun (setf ,name) (value array) (setf (,name array) value))))) (def %array-fill-pointer) (def %array-fill-pointer-p) (def %array-available-elements) (def %array-data-vector) (def %array-displacement) (def %array-displaced-p) (def %array-diplaced-from)) (defun %array-rank (array) (%array-rank array)) (defun %array-dimension (array axis) (%array-dimension array axis)) (defun %set-array-dimension (array axis value) (%set-array-dimension array axis value)) (defun %check-bound (array bound index) (declare (type index bound) (fixnum index)) (%check-bound array bound index)) (defun %with-array-data/fp (array start end) (%with-array-data-macro array start end :check-bounds t :check-fill-pointer t)) (defun %with-array-data (array start end) (%with-array-data-macro array start end :check-bounds t :check-fill-pointer nil)) (defun %data-vector-and-index (array index) (if (array-header-p array) (multiple-value-bind (vector index) (%with-array-data array index nil) (values vector index)) (values array index))) ;;;; MAKE-ARRAY (eval-when (:compile-toplevel :execute) (sb!xc:defmacro pick-vector-type (type &rest specs) `(cond ,@(mapcar (lambda (spec) `(,(if (eq (car spec) t) t `(subtypep ,type ',(car spec))) ,@(cdr spec))) specs)))) ;;; These functions are used in the implementation of MAKE-ARRAY for ;;; complex arrays. There are lots of transforms to simplify ;;; MAKE-ARRAY for various easy cases, but not for all reasonable ;;; cases, so e.g. as of sbcl-0.6.6 we still make full calls to ;;; MAKE-ARRAY for any non-simple array. Thus, there's some value to ;;; making this somewhat efficient, at least not doing full calls to ;;; SUBTYPEP in the easy cases. (defun %vector-widetag-and-n-bits (type) (case type ;; Pick off some easy common cases. ;; ;; (Perhaps we should make a much more exhaustive table of easy ;; common cases here. Or perhaps the effort would be better spent ;; on smarter compiler transforms which do the calculation once ;; and for all in any reasonable user programs.) ((t) (values #.sb!vm:simple-vector-widetag #.sb!vm:n-word-bits)) ((base-char standard-char #!-sb-unicode character) (values #.sb!vm:simple-base-string-widetag #.sb!vm:n-byte-bits)) #!+sb-unicode ((character) (values #.sb!vm:simple-character-string-widetag #.sb!vm:n-word-bits)) ((bit) (values #.sb!vm:simple-bit-vector-widetag 1)) ;; OK, we have to wade into SUBTYPEPing after all. (t (unless *type-system-initialized* (bug "SUBTYPEP dispatch for MAKE-ARRAY before the type system is ready")) #.`(pick-vector-type type ,@(map 'list (lambda (saetp) `(,(sb!vm:saetp-specifier saetp) (values ,(sb!vm:saetp-typecode saetp) ,(sb!vm:saetp-n-bits saetp)))) sb!vm:*specialized-array-element-type-properties*))))) (defun %complex-vector-widetag (type) (case type ;; Pick off some easy common cases. ((t) #.sb!vm:complex-vector-widetag) ((base-char #!-sb-unicode character) #.sb!vm:complex-base-string-widetag) #!+sb-unicode ((character) #.sb!vm:complex-character-string-widetag) ((nil) #.sb!vm:complex-vector-nil-widetag) ((bit) #.sb!vm:complex-bit-vector-widetag) ;; OK, we have to wade into SUBTYPEPing after all. (t (pick-vector-type type (nil #.sb!vm:complex-vector-nil-widetag) #!-sb-unicode (character #.sb!vm:complex-base-string-widetag) #!+sb-unicode (base-char #.sb!vm:complex-base-string-widetag) #!+sb-unicode (character #.sb!vm:complex-character-string-widetag) (bit #.sb!vm:complex-bit-vector-widetag) (t #.sb!vm:complex-vector-widetag))))) (defun make-array (dimensions &key (element-type t) (initial-element nil initial-element-p) (initial-contents nil initial-contents-p) adjustable fill-pointer displaced-to displaced-index-offset) (let* ((dimensions (if (listp dimensions) dimensions (list dimensions))) (array-rank (length (the list dimensions))) (simple (and (null fill-pointer) (not adjustable) (null displaced-to)))) (declare (fixnum array-rank)) (when (and displaced-index-offset (null displaced-to)) (error "can't specify :DISPLACED-INDEX-OFFSET without :DISPLACED-TO")) (when (and displaced-to (arrayp displaced-to) (not (equal (array-element-type displaced-to) (upgraded-array-element-type element-type)))) (error "Array element type of :DISPLACED-TO array does not match specified element type")) (if (and simple (= array-rank 1)) ;; it's a (SIMPLE-ARRAY * (*)) (multiple-value-bind (type n-bits) (%vector-widetag-and-n-bits element-type) (declare (type (unsigned-byte 8) type) (type (integer 0 256) n-bits)) (let* ((length (car dimensions)) (array (allocate-vector type length (ceiling (* (if (or (= type sb!vm:simple-base-string-widetag) #!+sb-unicode (= type sb!vm:simple-character-string-widetag)) (1+ length) length) n-bits) sb!vm:n-word-bits)))) (declare (type index length)) (when initial-element-p (fill array initial-element)) (when initial-contents-p (when initial-element-p (error "can't specify both :INITIAL-ELEMENT and ~ :INITIAL-CONTENTS")) (unless (= length (length initial-contents)) (error "There are ~W elements in the :INITIAL-CONTENTS, but ~ the vector length is ~W." (length initial-contents) length)) (replace array initial-contents)) array)) ;; it's either a complex array or a multidimensional array. (let* ((total-size (reduce #'* dimensions)) (data (or displaced-to (data-vector-from-inits dimensions total-size element-type initial-contents initial-contents-p initial-element initial-element-p))) (array (make-array-header (cond ((= array-rank 1) (%complex-vector-widetag element-type)) (simple sb!vm:simple-array-widetag) (t sb!vm:complex-array-widetag)) array-rank))) (cond (fill-pointer (unless (= array-rank 1) (error "Only vectors can have fill pointers.")) (let ((length (car dimensions))) (declare (fixnum length)) (setf (%array-fill-pointer array) (cond ((eq fill-pointer t) length) (t (unless (and (fixnump fill-pointer) (>= fill-pointer 0) (<= fill-pointer length)) ;; FIXME: should be TYPE-ERROR? (error "invalid fill-pointer ~W" fill-pointer)) fill-pointer)))) (setf (%array-fill-pointer-p array) t)) (t (setf (%array-fill-pointer array) total-size) (setf (%array-fill-pointer-p array) nil))) (setf (%array-available-elements array) total-size) (setf (%array-data-vector array) data) (setf (%array-displaced-from array) nil) (cond (displaced-to (when (or initial-element-p initial-contents-p) (error "Neither :INITIAL-ELEMENT nor :INITIAL-CONTENTS ~ can be specified along with :DISPLACED-TO")) (let ((offset (or displaced-index-offset 0))) (when (> (+ offset total-size) (array-total-size displaced-to)) (error "~S doesn't have enough elements." displaced-to)) (setf (%array-displacement array) offset) (setf (%array-displaced-p array) t) (%save-displaced-array-backpointer array data))) (t (setf (%array-displaced-p array) nil))) (let ((axis 0)) (dolist (dim dimensions) (setf (%array-dimension array axis) dim) (incf axis))) array)))) (defun make-static-vector (length &key (element-type '(unsigned-byte 8)) (initial-contents nil initial-contents-p) (initial-element nil initial-element-p)) "Allocate vector of LENGTH elements in static space. Only allocation of specialized arrays is supported." ;; STEP 1: check inputs fully ;; ;; This way of doing explicit checks before the vector is allocated ;; is expensive, but probably worth the trouble as once we've allocated ;; the vector we have no way to get rid of it anymore... (when (eq t (upgraded-array-element-type element-type)) (error "Static arrays of type ~S not supported." element-type)) (when initial-contents-p (when initial-element-p (error "can't specify both :INITIAL-ELEMENT and :INITIAL-CONTENTS")) (unless (= length (length initial-contents)) (error "There are ~W elements in the :INITIAL-CONTENTS, but the ~ vector length is ~W." (length initial-contents) length)) (unless (every (lambda (x) (typep x element-type)) initial-contents) (error ":INITIAL-CONTENTS contains elements not of type ~S." element-type))) (when initial-element-p (unless (typep initial-element element-type) (error ":INITIAL-ELEMENT ~S is not of type ~S." initial-element element-type))) ;; STEP 2 ;; ;; Allocate and possibly initialize the vector. (multiple-value-bind (type n-bits) (sb!impl::%vector-widetag-and-n-bits element-type) (let ((vector (allocate-static-vector type length (ceiling (* length n-bits) sb!vm:n-word-bits)))) (cond (initial-element-p (fill vector initial-element)) (initial-contents-p (replace vector initial-contents)) (t vector))))) ;;; DATA-VECTOR-FROM-INITS returns a simple vector that has the ;;; specified array characteristics. Dimensions is only used to pass ;;; to FILL-DATA-VECTOR for error checking on the structure of ;;; initial-contents. (defun data-vector-from-inits (dimensions total-size element-type initial-contents initial-contents-p initial-element initial-element-p) (when (and initial-contents-p initial-element-p) (error "cannot supply both :INITIAL-CONTENTS and :INITIAL-ELEMENT to either MAKE-ARRAY or ADJUST-ARRAY.")) (let ((data (if initial-element-p (make-array total-size :element-type element-type :initial-element initial-element) (make-array total-size :element-type element-type)))) (cond (initial-element-p (unless (simple-vector-p data) (unless (typep initial-element element-type) (error "~S cannot be used to initialize an array of type ~S." initial-element element-type)) (fill (the vector data) initial-element))) (initial-contents-p (fill-data-vector data dimensions initial-contents))) data)) (defun vector (&rest objects) #!+sb-doc "Construct a SIMPLE-VECTOR from the given objects." (coerce (the list objects) 'simple-vector)) ;;;; accessor/setter functions ;;; Dispatch to an optimized routine the data vector accessors for ;;; each different specialized vector type. Do dispatching by looking ;;; up the widetag in the array rather than with the typecases, which ;;; as of 1.0.5 compiles to a naive sequence of linear TYPEPs. Also ;;; provide separate versions where bounds checking has been moved ;;; from the callee to the caller, since it's much cheaper to do once ;;; the type information is available. Finally, for each of these ;;; routines also provide a slow path, taken for arrays that are not ;;; vectors or not simple. (macrolet ((def (name table-name) `(progn (defglobal ,table-name (make-array ,(1+ sb!vm:widetag-mask))) (defmacro ,name (array-var) `(the function (let ((tag 0)) (when (sb!vm::%other-pointer-p ,array-var) (setf tag (%other-pointer-widetag ,array-var))) (svref ,',table-name tag))))))) (def !find-data-vector-setter %%data-vector-setters%%) (def !find-data-vector-setter/check-bounds %%data-vector-setters/check-bounds%%) (def !find-data-vector-reffer %%data-vector-reffers%%) (def !find-data-vector-reffer/check-bounds %%data-vector-reffers/check-bounds%%)) (macrolet ((%ref (accessor-getter extra-params) `(funcall (,accessor-getter array) array index ,@extra-params)) (define (accessor-name slow-accessor-name accessor-getter extra-params check-bounds) `(progn (defun ,accessor-name (array index ,@extra-params) (declare (optimize speed ;; (SAFETY 0) is ok. All calls to ;; these functions are generated by ;; the compiler, so argument count ;; checking isn't needed. Type checking ;; is done implicitly via the widetag ;; dispatch. (safety 0))) (%ref ,accessor-getter ,extra-params)) (defun ,slow-accessor-name (array index ,@extra-params) (declare (optimize speed (safety 0))) (if (not (%array-displaced-p array)) ;; The reasonably quick path of non-displaced complex ;; arrays. (let ((array (%array-data-vector array))) (%ref ,accessor-getter ,extra-params)) ;; The real slow path. (with-array-data ((vector array) (index (locally (declare (optimize (speed 1) (safety 1))) (,@check-bounds index))) (end) :force-inline t) (declare (ignore end)) (,accessor-name vector index ,@extra-params))))))) (define hairy-data-vector-ref slow-hairy-data-vector-ref !find-data-vector-reffer nil (progn)) (define hairy-data-vector-set slow-hairy-data-vector-set !find-data-vector-setter (new-value) (progn)) (define hairy-data-vector-ref/check-bounds slow-hairy-data-vector-ref/check-bounds !find-data-vector-reffer/check-bounds nil (%check-bound array (array-dimension array 0))) (define hairy-data-vector-set/check-bounds slow-hairy-data-vector-set/check-bounds !find-data-vector-setter/check-bounds (new-value) (%check-bound array (array-dimension array 0)))) (defun hairy-ref-error (array index &optional new-value) (declare (ignore index new-value)) (error 'type-error :datum array :expected-type 'vector)) ;;; Populate the dispatch tables. (macrolet ((define-reffer (saetp check-form) (let* ((type (sb!vm:saetp-specifier saetp)) (atype `(simple-array ,type (*)))) `(named-lambda optimized-data-vector-ref (vector index) (declare (optimize speed (safety 0))) (data-vector-ref (the ,atype vector) (locally (declare (optimize (safety 1))) (the index (,@check-form index))))))) (define-setter (saetp check-form) (let* ((type (sb!vm:saetp-specifier saetp)) (atype `(simple-array ,type (*)))) `(named-lambda optimized-data-vector-set (vector index new-value) (declare (optimize speed (safety 0))) (data-vector-set (the ,atype vector) (locally (declare (optimize (safety 1))) (the index (,@check-form index))) (locally ;; SPEED 1 needed to avoid the compiler ;; from downgrading the type check to ;; a cheaper one. (declare (optimize (speed 1) (safety 1))) (the ,type new-value))) ;; For specialized arrays, the return from ;; data-vector-set would have to be reboxed to be a ;; (Lisp) return value; instead, we use the ;; already-boxed value as the return. new-value))) (define-reffers (symbol deffer check-form slow-path) `(progn ;; FIXME/KLUDGE: can't just FILL here, because genesis doesn't ;; preserve the binding, so re-initiaize as NS doesn't have ;; the energy to figure out to change that right now. (setf ,symbol (make-array (1+ sb!vm::widetag-mask) :initial-element #'hairy-ref-error)) ,@(loop for widetag in '(sb!vm:complex-vector-widetag sb!vm:complex-vector-nil-widetag sb!vm:complex-bit-vector-widetag #!+sb-unicode sb!vm:complex-character-string-widetag sb!vm:complex-base-string-widetag sb!vm:simple-array-widetag sb!vm:complex-array-widetag) collect `(setf (svref ,symbol ,widetag) ,slow-path)) ,@(loop for saetp across sb!vm:*specialized-array-element-type-properties* for widetag = (sb!vm:saetp-typecode saetp) collect `(setf (svref ,symbol ,widetag) (,deffer ,saetp ,check-form)))))) (defun !hairy-data-vector-reffer-init () (define-reffers %%data-vector-reffers%% define-reffer (progn) #'slow-hairy-data-vector-ref) (define-reffers %%data-vector-setters%% define-setter (progn) #'slow-hairy-data-vector-set) (define-reffers %%data-vector-reffers/check-bounds%% define-reffer (%check-bound vector (length vector)) #'slow-hairy-data-vector-ref/check-bounds) (define-reffers %%data-vector-setters/check-bounds%% define-setter (%check-bound vector (length vector)) #'slow-hairy-data-vector-set/check-bounds))) ;;; (Ordinary DATA-VECTOR-REF usage compiles into a vop, but ;;; DATA-VECTOR-REF is also FOLDABLE, and this ordinary function ;;; definition is needed for the compiler to use in constant folding.) (defun data-vector-ref (array index) (hairy-data-vector-ref array index)) (defun data-vector-ref-with-offset (array index offset) (hairy-data-vector-ref array (+ index offset))) (defun invalid-array-p (array) (and (array-header-p array) (consp (%array-displaced-p array)))) (declaim (ftype (function (array) nil) invalid-array-error)) (defun invalid-array-error (array) (aver (array-header-p array)) ;; Array invalidation stashes the original dimensions here... (let ((dims (%array-displaced-p array)) (et (array-element-type array))) (error 'invalid-array-error :datum array :expected-type (if (cdr dims) `(array ,et ,dims) `(vector ,et ,@dims))))) (declaim (ftype (function (array integer integer &optional t) nil) invalid-array-index-error)) (defun invalid-array-index-error (array index bound &optional axis) (if (invalid-array-p array) (invalid-array-error array) (error 'invalid-array-index-error :array array :axis axis :datum index :expected-type `(integer 0 (,bound))))) ;;; SUBSCRIPTS has a dynamic-extent list structure and is destroyed (defun %array-row-major-index (array subscripts &optional (invalid-index-error-p t)) (declare (array array) (list subscripts)) (let ((rank (array-rank array))) (unless (= rank (length subscripts)) (error "wrong number of subscripts, ~W, for array of rank ~W" (length subscripts) rank)) (if (array-header-p array) (do ((subs (nreverse subscripts) (cdr subs)) (axis (1- (array-rank array)) (1- axis)) (chunk-size 1) (result 0)) ((null subs) result) (declare (list subs) (fixnum axis chunk-size result)) (let ((index (car subs)) (dim (%array-dimension array axis))) (declare (fixnum dim)) (unless (and (fixnump index) (< -1 index dim)) (if invalid-index-error-p (invalid-array-index-error array index dim axis) (return-from %array-row-major-index nil))) (incf result (* chunk-size (the fixnum index))) (setf chunk-size (* chunk-size dim)))) (let ((index (first subscripts)) (length (length (the (simple-array * (*)) array)))) (unless (and (fixnump index) (< -1 index length)) (if invalid-index-error-p (invalid-array-index-error array index length) (return-from %array-row-major-index nil))) index)))) (defun array-in-bounds-p (array &rest subscripts) #!+sb-doc "Return T if the SUBSCRIPTS are in bounds for the ARRAY, NIL otherwise." (if (%array-row-major-index array subscripts nil) t)) (defun array-row-major-index (array &rest subscripts) (declare (truly-dynamic-extent subscripts)) (%array-row-major-index array subscripts)) (defun aref (array &rest subscripts) #!+sb-doc "Return the element of the ARRAY specified by the SUBSCRIPTS." (declare (truly-dynamic-extent subscripts)) (row-major-aref array (%array-row-major-index array subscripts))) (defun %aset (array &rest stuff) (declare (truly-dynamic-extent stuff)) (let ((subscripts (butlast stuff)) (new-value (car (last stuff)))) (setf (row-major-aref array (%array-row-major-index array subscripts)) new-value))) ;;; FIXME: What's supposed to happen with functions ;;; like AREF when we (DEFUN (SETF FOO) ..) when ;;; DEFSETF FOO is also defined? It seems as though the logical ;;; thing to do would be to nuke the macro definition for (SETF FOO) ;;; and replace it with the (SETF FOO) function, issuing a warning, ;;; just as for ordinary functions ;;; * (LISP-IMPLEMENTATION-VERSION) ;;; "18a+ release x86-linux 2.4.7 6 November 1998 cvs" ;;; * (DEFMACRO ZOO (X) `(+ ,X ,X)) ;;; ZOO ;;; * (DEFUN ZOO (X) (* 3 X)) ;;; Warning: ZOO previously defined as a macro. ;;; ZOO ;;; But that doesn't seem to be what happens in CMU CL. ;;; ;;; KLUDGE: this is probably because ANSI, in its wisdom (CLHS ;;; 5.1.2.5) requires implementations to support ;;; (SETF (APPLY #'AREF ...) ...) ;;; [and also #'BIT and #'SBIT]. Yes, this is terrifying, and it's ;;; also terrifying that this sequence of definitions causes it to ;;; work. ;;; ;;; Also, it would be nice to make DESCRIBE FOO tell whether a symbol ;;; has a setf expansion and/or a setf function defined. #!-sb-fluid (declaim (inline (setf aref))) (defun (setf aref) (new-value array &rest subscripts) (declare (truly-dynamic-extent subscripts)) (declare (type array array)) (setf (row-major-aref array (%array-row-major-index array subscripts)) new-value)) (defun row-major-aref (array index) #!+sb-doc "Return the element of array corressponding to the row-major index. This is SETF'able." (declare (optimize (safety 1))) (row-major-aref array index)) (defun %set-row-major-aref (array index new-value) (declare (optimize (safety 1))) (setf (row-major-aref array index) new-value)) (defun svref (simple-vector index) #!+sb-doc "Return the INDEX'th element of the given Simple-Vector." (declare (optimize (safety 1))) (aref simple-vector index)) (defun %svset (simple-vector index new) (declare (optimize (safety 1))) (setf (aref simple-vector index) new)) (defun bit (bit-array &rest subscripts) #!+sb-doc "Return the bit from the BIT-ARRAY at the specified SUBSCRIPTS." (declare (type (array bit) bit-array) (optimize (safety 1))) (row-major-aref bit-array (%array-row-major-index bit-array subscripts))) (defun %bitset (bit-array &rest stuff) (declare (type (array bit) bit-array) (optimize (safety 1))) (let ((subscripts (butlast stuff)) (new-value (car (last stuff)))) (setf (row-major-aref bit-array (%array-row-major-index bit-array subscripts)) new-value))) #!-sb-fluid (declaim (inline (setf bit))) (defun (setf bit) (new-value bit-array &rest subscripts) (declare (type (array bit) bit-array) (optimize (safety 1))) (setf (row-major-aref bit-array (%array-row-major-index bit-array subscripts)) new-value)) (defun sbit (simple-bit-array &rest subscripts) #!+sb-doc "Return the bit from SIMPLE-BIT-ARRAY at the specified SUBSCRIPTS." (declare (type (simple-array bit) simple-bit-array) (optimize (safety 1))) (row-major-aref simple-bit-array (%array-row-major-index simple-bit-array subscripts))) ;;; KLUDGE: Not all these things (%SET-ROW-MAJOR-AREF, %SET-FILL-POINTER, ;;; %SET-FDEFINITION, %SCHARSET, %SBITSET..) seem to deserve separate names. ;;; Could we just DEFUN (SETF SBIT) etc. and get rid of the non-ANSI names? ;;; -- WHN 19990911 (defun %sbitset (simple-bit-array &rest stuff) (declare (type (simple-array bit) simple-bit-array) (optimize (safety 1))) (let ((subscripts (butlast stuff)) (new-value (car (last stuff)))) (setf (row-major-aref simple-bit-array (%array-row-major-index simple-bit-array subscripts)) new-value))) #!-sb-fluid (declaim (inline (setf sbit))) (defun (setf sbit) (new-value bit-array &rest subscripts) (declare (type (simple-array bit) bit-array) (optimize (safety 1))) (setf (row-major-aref bit-array (%array-row-major-index bit-array subscripts)) new-value)) ;;;; miscellaneous array properties (defun array-element-type (array) #!+sb-doc "Return the type of the elements of the array" (let ((widetag (widetag-of array))) (macrolet ((pick-element-type (&rest stuff) `(cond ,@(mapcar (lambda (stuff) (cons (let ((item (car stuff))) (cond ((eq item t) t) ((listp item) (cons 'or (mapcar (lambda (x) `(= widetag ,x)) item))) (t `(= widetag ,item)))) (cdr stuff))) stuff)))) #.`(pick-element-type ,@(map 'list (lambda (saetp) `(,(if (sb!vm:saetp-complex-typecode saetp) (list (sb!vm:saetp-typecode saetp) (sb!vm:saetp-complex-typecode saetp)) (sb!vm:saetp-typecode saetp)) ',(sb!vm:saetp-specifier saetp))) sb!vm:*specialized-array-element-type-properties*) ((sb!vm:simple-array-widetag sb!vm:complex-vector-widetag sb!vm:complex-array-widetag) (with-array-data ((array array) (start) (end)) (declare (ignore start end)) (array-element-type array))) (t (error 'type-error :datum array :expected-type 'array)))))) (defun array-rank (array) #!+sb-doc "Return the number of dimensions of ARRAY." (if (array-header-p array) (%array-rank array) 1)) (defun array-dimension (array axis-number) #!+sb-doc "Return the length of dimension AXIS-NUMBER of ARRAY." (declare (array array) (type index axis-number)) (cond ((not (array-header-p array)) (unless (= axis-number 0) (error "Vector axis is not zero: ~S" axis-number)) (length (the (simple-array * (*)) array))) ((>= axis-number (%array-rank array)) (error "Axis number ~W is too big; ~S only has ~D dimension~:P." axis-number array (%array-rank array))) (t (%array-dimension array axis-number)))) (defun array-dimensions (array) #!+sb-doc "Return a list whose elements are the dimensions of the array" (declare (array array)) (if (array-header-p array) (do ((results nil (cons (array-dimension array index) results)) (index (1- (array-rank array)) (1- index))) ((minusp index) results)) (list (array-dimension array 0)))) (defun array-total-size (array) #!+sb-doc "Return the total number of elements in the Array." (declare (array array)) (if (array-header-p array) (%array-available-elements array) (length (the vector array)))) (defun array-displacement (array) #!+sb-doc "Return the values of :DISPLACED-TO and :DISPLACED-INDEX-offset options to MAKE-ARRAY, or NIL and 0 if not a displaced array." (declare (type array array)) (if (and (array-header-p array) ; if unsimple and (%array-displaced-p array)) ; displaced (values (%array-data-vector array) (%array-displacement array)) (values nil 0))) (defun adjustable-array-p (array) #!+sb-doc "Return T if (ADJUST-ARRAY ARRAY...) would return an array identical to the argument, this happens for complex arrays." (declare (array array)) ;; Note that this appears not to be a fundamental limitation. ;; non-vector SIMPLE-ARRAYs are in fact capable of being adjusted, ;; but in practice we test using ADJUSTABLE-ARRAY-P in ADJUST-ARRAY. ;; -- CSR, 2004-03-01. (not (typep array 'simple-array))) ;;;; fill pointer frobbing stuff (declaim (inline array-has-fill-pointer-p)) (defun array-has-fill-pointer-p (array) #!+sb-doc "Return T if the given ARRAY has a fill pointer, or NIL otherwise." (declare (array array)) (and (array-header-p array) (%array-fill-pointer-p array))) (defun fill-pointer-error (vector arg) (cond (arg (aver (array-has-fill-pointer-p vector)) (let ((max (%array-available-elements vector))) (error 'simple-type-error :datum arg :expected-type (list 'integer 0 max) :format-control "The new fill pointer, ~S, is larger than the length of the vector (~S.)" :format-arguments (list arg max)))) (t (error 'simple-type-error :datum vector :expected-type '(and vector (satisfies array-has-fill-pointer-p)) :format-control "~S is not an array with a fill pointer." :format-arguments (list vector))))) (declaim (inline fill-pointer)) (defun fill-pointer (vector) #!+sb-doc "Return the FILL-POINTER of the given VECTOR." (if (array-has-fill-pointer-p vector) (%array-fill-pointer vector) (fill-pointer-error vector nil))) (defun %set-fill-pointer (vector new) (flet ((oops (x) (fill-pointer-error vector x))) (if (array-has-fill-pointer-p vector) (if (> new (%array-available-elements vector)) (oops new) (setf (%array-fill-pointer vector) new)) (oops nil)))) ;;; FIXME: It'd probably make sense to use a MACROLET to share the ;;; guts of VECTOR-PUSH between VECTOR-PUSH-EXTEND. Such a macro ;;; should probably be based on the VECTOR-PUSH-EXTEND code (which is ;;; new ca. sbcl-0.7.0) rather than the VECTOR-PUSH code (which dates ;;; back to CMU CL). (defun vector-push (new-el array) #!+sb-doc "Attempt to set the element of ARRAY designated by its fill pointer to NEW-EL, and increment the fill pointer by one. If the fill pointer is too large, NIL is returned, otherwise the index of the pushed element is returned." (let ((fill-pointer (fill-pointer array))) (declare (fixnum fill-pointer)) (cond ((= fill-pointer (%array-available-elements array)) nil) (t (locally (declare (optimize (safety 0))) (setf (aref array fill-pointer) new-el)) (setf (%array-fill-pointer array) (1+ fill-pointer)) fill-pointer)))) (defun vector-push-extend (new-element vector &optional (min-extension (let ((length (length vector))) (min (1+ length) (- array-dimension-limit length))))) (declare (fixnum min-extension)) (let ((fill-pointer (fill-pointer vector))) (declare (fixnum fill-pointer)) (when (= fill-pointer (%array-available-elements vector)) (adjust-array vector (+ fill-pointer (max 1 min-extension)))) ;; disable bounds checking (locally (declare (optimize (safety 0))) (setf (aref vector fill-pointer) new-element)) (setf (%array-fill-pointer vector) (1+ fill-pointer)) fill-pointer)) (defun vector-pop (array) #!+sb-doc "Decrease the fill pointer by 1 and return the element pointed to by the new fill pointer." (let ((fill-pointer (fill-pointer array))) (declare (fixnum fill-pointer)) (if (zerop fill-pointer) (error "There is nothing left to pop.") ;; disable bounds checking (and any fixnum test) (locally (declare (optimize (safety 0))) (aref array (setf (%array-fill-pointer array) (1- fill-pointer))))))) ;;;; ADJUST-ARRAY (defun adjust-array (array dimensions &key (element-type (array-element-type array)) (initial-element nil initial-element-p) (initial-contents nil initial-contents-p) fill-pointer displaced-to displaced-index-offset) #!+sb-doc "Adjust ARRAY's dimensions to the given DIMENSIONS and stuff." (when (invalid-array-p array) (invalid-array-error array)) (let ((dimensions (if (listp dimensions) dimensions (list dimensions)))) (cond ((/= (the fixnum (length (the list dimensions))) (the fixnum (array-rank array))) (error "The number of dimensions not equal to rank of array.")) ((not (subtypep element-type (array-element-type array))) (error "The new element type, ~S, is incompatible with old type." element-type)) ((and fill-pointer (not (array-has-fill-pointer-p array))) (error 'type-error :datum array :expected-type '(satisfies array-has-fill-pointer-p)))) (let ((array-rank (length (the list dimensions)))) (declare (fixnum array-rank)) (unless (= array-rank 1) (when fill-pointer (error "Only vectors can have fill pointers."))) (cond (initial-contents-p ;; array former contents replaced by INITIAL-CONTENTS (if (or initial-element-p displaced-to) (error "INITIAL-CONTENTS may not be specified with ~ the :INITIAL-ELEMENT or :DISPLACED-TO option.")) (let* ((array-size (apply #'* dimensions)) (array-data (data-vector-from-inits dimensions array-size element-type initial-contents initial-contents-p initial-element initial-element-p))) (if (adjustable-array-p array) (set-array-header array array-data array-size (get-new-fill-pointer array array-size fill-pointer) 0 dimensions nil nil) (if (array-header-p array) ;; simple multidimensional or single dimensional array (make-array dimensions :element-type element-type :initial-contents initial-contents) array-data)))) (displaced-to ;; We already established that no INITIAL-CONTENTS was supplied. (when initial-element (error "The :INITIAL-ELEMENT option may not be specified ~ with :DISPLACED-TO.")) (unless (subtypep element-type (array-element-type displaced-to)) (error "can't displace an array of type ~S into another of ~ type ~S" element-type (array-element-type displaced-to))) (let ((displacement (or displaced-index-offset 0)) (array-size (apply #'* dimensions))) (declare (fixnum displacement array-size)) (if (< (the fixnum (array-total-size displaced-to)) (the fixnum (+ displacement array-size))) (error "The :DISPLACED-TO array is too small.")) (if (adjustable-array-p array) ;; None of the original contents appear in adjusted array. (set-array-header array displaced-to array-size (get-new-fill-pointer array array-size fill-pointer) displacement dimensions t nil) ;; simple multidimensional or single dimensional array (make-array dimensions :element-type element-type :displaced-to displaced-to :displaced-index-offset displaced-index-offset)))) ((= array-rank 1) (let ((old-length (array-total-size array)) (new-length (car dimensions)) new-data) (declare (fixnum old-length new-length)) (with-array-data ((old-data array) (old-start) (old-end old-length)) (cond ((or (and (array-header-p array) (%array-displaced-p array)) (< old-length new-length)) (setf new-data (data-vector-from-inits dimensions new-length element-type initial-contents initial-contents-p initial-element initial-element-p)) (replace new-data old-data :start2 old-start :end2 old-end)) (t (setf new-data (shrink-vector old-data new-length)))) (if (adjustable-array-p array) (set-array-header array new-data new-length (get-new-fill-pointer array new-length fill-pointer) 0 dimensions nil nil) new-data)))) (t (let ((old-length (%array-available-elements array)) (new-length (apply #'* dimensions))) (declare (fixnum old-length new-length)) (with-array-data ((old-data array) (old-start) (old-end old-length)) (declare (ignore old-end)) (let ((new-data (if (or (and (array-header-p array) (%array-displaced-p array)) (> new-length old-length)) (data-vector-from-inits dimensions new-length element-type () nil initial-element initial-element-p) old-data))) (if (or (zerop old-length) (zerop new-length)) (when initial-element-p (fill new-data initial-element)) (zap-array-data old-data (array-dimensions array) old-start new-data dimensions new-length element-type initial-element initial-element-p)) (if (adjustable-array-p array) (set-array-header array new-data new-length nil 0 dimensions nil nil) (let ((new-array (make-array-header sb!vm:simple-array-widetag array-rank))) (set-array-header new-array new-data new-length nil 0 dimensions nil t))))))))))) (defun get-new-fill-pointer (old-array new-array-size fill-pointer) (cond ((not fill-pointer) (when (array-has-fill-pointer-p old-array) (when (> (%array-fill-pointer old-array) new-array-size) (error "cannot ADJUST-ARRAY an array (~S) to a size (~S) that is ~ smaller than its fill pointer (~S)" old-array new-array-size (fill-pointer old-array))) (%array-fill-pointer old-array))) ((not (array-has-fill-pointer-p old-array)) (error "cannot supply a non-NIL value (~S) for :FILL-POINTER ~ in ADJUST-ARRAY unless the array (~S) was originally ~ created with a fill pointer" fill-pointer old-array)) ((numberp fill-pointer) (when (> fill-pointer new-array-size) (error "can't supply a value for :FILL-POINTER (~S) that is larger ~ than the new length of the vector (~S)" fill-pointer new-array-size)) fill-pointer) ((eq fill-pointer t) new-array-size) (t (error "bogus value for :FILL-POINTER in ADJUST-ARRAY: ~S" fill-pointer)))) ;;; Destructively alter VECTOR, changing its length to NEW-LENGTH, ;;; which must be less than or equal to its current length. This can ;;; be called on vectors without a fill pointer but it is extremely ;;; dangerous to do so: shrinking the size of an object (as viewed by ;;; the gc) makes bounds checking unreliable in the face of interrupts ;;; or multi-threading. Call it only on provably local vectors. (defun %shrink-vector (vector new-length) (declare (vector vector)) (unless (array-header-p vector) (macrolet ((frob (name &rest things) `(etypecase ,name ((simple-array nil (*)) (error 'nil-array-accessed-error)) ,@(mapcar (lambda (thing) (destructuring-bind (type-spec fill-value) thing `(,type-spec (fill (truly-the ,type-spec ,name) ,fill-value :start new-length)))) things)))) ;; Set the 'tail' of the vector to the appropriate type of zero, ;; "because in some cases we'll scavenge larger areas in one go, ;; like groups of pages that had triggered the write barrier, or ;; the whole static space" according to jsnell. #.`(frob vector ,@(map 'list (lambda (saetp) `((simple-array ,(sb!vm:saetp-specifier saetp) (*)) ,(if (or (eq (sb!vm:saetp-specifier saetp) 'character) #!+sb-unicode (eq (sb!vm:saetp-specifier saetp) 'base-char)) *default-init-char-form* (sb!vm:saetp-initial-element-default saetp)))) (remove-if-not #'sb!vm:saetp-specifier sb!vm:*specialized-array-element-type-properties*))))) ;; Only arrays have fill-pointers, but vectors have their length ;; parameter in the same place. (setf (%array-fill-pointer vector) new-length) vector) (defun shrink-vector (vector new-length) (declare (vector vector)) (cond ((eq (length vector) new-length) vector) ((array-has-fill-pointer-p vector) (setf (%array-fill-pointer vector) new-length) vector) (t (subseq vector 0 new-length)))) ;;; BIG THREAD SAFETY NOTE ;;; ;;; ADJUST-ARRAY/SET-ARRAY-HEADER, and its callees are very ;;; thread unsafe. They are nonatomic, and can mess with parallel ;;; code using the same arrays. ;;; ;;; A likely seeming fix is an additional level of indirection: ;;; ARRAY-HEADER -> ARRAY-INFO -> ... where ARRAY-HEADER would ;;; hold nothing but the pointer to ARRAY-INFO, and ARRAY-INFO ;;; would hold everything ARRAY-HEADER now holds. This allows ;;; consing up a new ARRAY-INFO and replacing it atomically in ;;; the ARRAY-HEADER. ;;; ;;; %WALK-DISPLACED-ARRAY-BACKPOINTERS is an especially nasty ;;; one: not only is it needed extremely rarely, which makes ;;; any thread safety bugs involving it look like rare random ;;; corruption, but because it walks the chain *upwards*, which ;;; may violate user expectations. (defun %save-displaced-array-backpointer (array data) (flet ((purge (pointers) (remove-if (lambda (value) (or (not value) (eq array value))) pointers :key #'weak-pointer-value))) ;; Add backpointer to the new data vector if it has a header. (when (array-header-p data) (setf (%array-displaced-from data) (cons (make-weak-pointer array) (purge (%array-displaced-from data))))) ;; Remove old backpointer, if any. (let ((old-data (%array-data-vector array))) (when (and (neq data old-data) (array-header-p old-data)) (setf (%array-displaced-from old-data) (purge (%array-displaced-from old-data))))))) (defun %walk-displaced-array-backpointers (array new-length) (dolist (p (%array-displaced-from array)) (let ((from (weak-pointer-value p))) (when (and from (eq array (%array-data-vector from))) (let ((requires (+ (%array-available-elements from) (%array-displacement from)))) (unless (>= new-length requires) ;; ANSI sayeth (ADJUST-ARRAY dictionary entry): ;; ;; "If A is displaced to B, the consequences are unspecified if B is ;; adjusted in such a way that it no longer has enough elements to ;; satisfy A. ;; ;; since we're hanging on a weak pointer here, we can't signal an ;; error right now: the array that we're looking at might be ;; garbage. Instead, we set all dimensions to zero so that next ;; safe access to the displaced array will trap. Additionally, we ;; save the original dimensions, so we can signal a more ;; understandable error when the time comes. (%walk-displaced-array-backpointers from 0) (setf (%array-fill-pointer from) 0 (%array-available-elements from) 0 (%array-displaced-p from) (array-dimensions array)) (dotimes (i (%array-rank from)) (setf (%array-dimension from i) 0)))))))) ;;; Fill in array header with the provided information, and return the array. (defun set-array-header (array data length fill-pointer displacement dimensions displacedp newp) (if newp (setf (%array-displaced-from array) nil) (%walk-displaced-array-backpointers array length)) (when displacedp (%save-displaced-array-backpointer array data)) (setf (%array-data-vector array) data) (setf (%array-available-elements array) length) (cond (fill-pointer (setf (%array-fill-pointer array) fill-pointer) (setf (%array-fill-pointer-p array) t)) (t (setf (%array-fill-pointer array) length) (setf (%array-fill-pointer-p array) nil))) (setf (%array-displacement array) displacement) (if (listp dimensions) (dotimes (axis (array-rank array)) (declare (type index axis)) (setf (%array-dimension array axis) (pop dimensions))) (setf (%array-dimension array 0) dimensions)) (setf (%array-displaced-p array) displacedp) array) ;;; User visible extension (declaim (ftype (function (array) (values (simple-array * (*)) &optional)) array-storage-vector)) (defun array-storage-vector (array) "Returns the underlying storage vector of ARRAY, which must be a non-displaced array. In SBCL, if ARRAY is a of type \(SIMPLE-ARRAY * \(*)), it is its own storage vector. Multidimensional arrays, arrays with fill pointers, and adjustable arrays have an underlying storage vector with the same ARRAY-ELEMENT-TYPE as ARRAY, which this function returns. Important note: the underlying vector is an implementation detail. Even though this function exposes it, changes in the implementation may cause this function to be removed without further warning." ;; KLUDGE: Without TRULY-THE the system is not smart enough to figure out that ;; the return value is always of the known type. (truly-the (simple-array * (*)) (if (array-header-p array) (if (%array-displaced-p array) (error "~S cannot be used with displaced arrays. Use ~S instead." 'array-storage-vector 'array-displacement) (%array-data-vector array)) array))) ;;;; ZAP-ARRAY-DATA for ADJUST-ARRAY ;;; This does the grinding work for ADJUST-ARRAY. It zaps the data ;;; from the OLD-DATA in an arrangement specified by the OLD-DIMS to ;;; the NEW-DATA in an arrangement specified by the NEW-DIMS. OFFSET ;;; is a displaced offset to be added to computed indices of OLD-DATA. (defun zap-array-data (old-data old-dims offset new-data new-dims new-length element-type initial-element initial-element-p) (declare (list old-dims new-dims) (fixnum new-length)) ;; OLD-DIMS comes from array-dimensions, which returns a fresh list ;; at least in SBCL. ;; NEW-DIMS comes from the user. (setf old-dims (nreverse old-dims) new-dims (reverse new-dims)) (cond ((eq old-data new-data) ;; NEW-LENGTH, ELEMENT-TYPE, INITIAL-ELEMENT, and ;; INITIAL-ELEMENT-P are used when OLD-DATA and NEW-DATA are ;; EQ; in this case, a temporary must be used and filled ;; appropriately. specified initial-element. (when initial-element-p ;; FIXME: transforming this TYPEP to someting a bit faster ;; would be a win... (unless (typep initial-element element-type) (error "~S can't be used to initialize an array of type ~S." initial-element element-type))) (let ((temp (if initial-element-p (make-array new-length :initial-element initial-element) (make-array new-length)))) (declare (simple-vector temp)) (zap-array-data-aux old-data old-dims offset temp new-dims) (dotimes (i new-length) (setf (aref new-data i) (aref temp i))) ;; Kill the temporary vector to prevent garbage retention. (%shrink-vector temp 0))) (t ;; When OLD-DATA and NEW-DATA are not EQ, NEW-DATA has ;; already been filled with any (zap-array-data-aux old-data old-dims offset new-data new-dims)))) (defun zap-array-data-aux (old-data old-dims offset new-data new-dims) (declare (fixnum offset)) (let ((limits (mapcar (lambda (x y) (declare (fixnum x y)) (1- (the fixnum (min x y)))) old-dims new-dims))) (macrolet ((bump-index-list (index limits) `(do ((subscripts ,index (cdr subscripts)) (limits ,limits (cdr limits))) ((null subscripts) :eof) (cond ((< (the fixnum (car subscripts)) (the fixnum (car limits))) (rplaca subscripts (1+ (the fixnum (car subscripts)))) (return ,index)) (t (rplaca subscripts 0)))))) (do ((index (make-list (length old-dims) :initial-element 0) (bump-index-list index limits))) ((eq index :eof)) (setf (aref new-data (row-major-index-from-dims index new-dims)) (aref old-data (+ (the fixnum (row-major-index-from-dims index old-dims)) offset))))))) ;;; Figure out the row-major-order index of an array reference from a ;;; list of subscripts and a list of dimensions. This is for internal ;;; calls only, and the subscripts and dim-list variables are assumed ;;; to be reversed from what the user supplied. (defun row-major-index-from-dims (rev-subscripts rev-dim-list) (do ((rev-subscripts rev-subscripts (cdr rev-subscripts)) (rev-dim-list rev-dim-list (cdr rev-dim-list)) (chunk-size 1) (result 0)) ((null rev-dim-list) result) (declare (fixnum chunk-size result)) (setq result (+ result (the fixnum (* (the fixnum (car rev-subscripts)) chunk-size)))) (setq chunk-size (* chunk-size (the fixnum (car rev-dim-list)))))) ;;;; some bit stuff (defun bit-array-same-dimensions-p (array1 array2) (declare (type (array bit) array1 array2)) (and (= (array-rank array1) (array-rank array2)) (dotimes (index (array-rank array1) t) (when (/= (array-dimension array1 index) (array-dimension array2 index)) (return nil))))) (defun pick-result-array (result-bit-array bit-array-1) (case result-bit-array ((t) bit-array-1) ((nil) (make-array (array-dimensions bit-array-1) :element-type 'bit :initial-element 0)) (t (unless (bit-array-same-dimensions-p bit-array-1 result-bit-array) (error "~S and ~S don't have the same dimensions." bit-array-1 result-bit-array)) result-bit-array))) (defmacro def-bit-array-op (name function) `(defun ,name (bit-array-1 bit-array-2 &optional result-bit-array) #!+sb-doc ,(format nil "Perform a bit-wise ~A on the elements of BIT-ARRAY-1 and ~ BIT-ARRAY-2,~% putting the results in RESULT-BIT-ARRAY. ~ If RESULT-BIT-ARRAY is T,~% BIT-ARRAY-1 is used. If ~ RESULT-BIT-ARRAY is NIL or omitted, a new array is~% created. ~ All the arrays must have the same rank and dimensions." (symbol-name function)) (declare (type (array bit) bit-array-1 bit-array-2) (type (or (array bit) (member t nil)) result-bit-array)) (unless (bit-array-same-dimensions-p bit-array-1 bit-array-2) (error "~S and ~S don't have the same dimensions." bit-array-1 bit-array-2)) (let ((result-bit-array (pick-result-array result-bit-array bit-array-1))) (if (and (simple-bit-vector-p bit-array-1) (simple-bit-vector-p bit-array-2) (simple-bit-vector-p result-bit-array)) (locally (declare (optimize (speed 3) (safety 0))) (,name bit-array-1 bit-array-2 result-bit-array)) (with-array-data ((data1 bit-array-1) (start1) (end1)) (declare (ignore end1)) (with-array-data ((data2 bit-array-2) (start2) (end2)) (declare (ignore end2)) (with-array-data ((data3 result-bit-array) (start3) (end3)) (do ((index-1 start1 (1+ index-1)) (index-2 start2 (1+ index-2)) (index-3 start3 (1+ index-3))) ((>= index-3 end3) result-bit-array) (declare (type index index-1 index-2 index-3)) (setf (sbit data3 index-3) (logand (,function (sbit data1 index-1) (sbit data2 index-2)) 1)))))))))) (def-bit-array-op bit-and logand) (def-bit-array-op bit-ior logior) (def-bit-array-op bit-xor logxor) (def-bit-array-op bit-eqv logeqv) (def-bit-array-op bit-nand lognand) (def-bit-array-op bit-nor lognor) (def-bit-array-op bit-andc1 logandc1) (def-bit-array-op bit-andc2 logandc2) (def-bit-array-op bit-orc1 logorc1) (def-bit-array-op bit-orc2 logorc2) (defun bit-not (bit-array &optional result-bit-array) #!+sb-doc "Performs a bit-wise logical NOT on the elements of BIT-ARRAY, putting the results in RESULT-BIT-ARRAY. If RESULT-BIT-ARRAY is T, BIT-ARRAY is used. If RESULT-BIT-ARRAY is NIL or omitted, a new array is created. Both arrays must have the same rank and dimensions." (declare (type (array bit) bit-array) (type (or (array bit) (member t nil)) result-bit-array)) (let ((result-bit-array (pick-result-array result-bit-array bit-array))) (if (and (simple-bit-vector-p bit-array) (simple-bit-vector-p result-bit-array)) (locally (declare (optimize (speed 3) (safety 0))) (bit-not bit-array result-bit-array)) (with-array-data ((src bit-array) (src-start) (src-end)) (declare (ignore src-end)) (with-array-data ((dst result-bit-array) (dst-start) (dst-end)) (do ((src-index src-start (1+ src-index)) (dst-index dst-start (1+ dst-index))) ((>= dst-index dst-end) result-bit-array) (declare (type index src-index dst-index)) (setf (sbit dst dst-index) (logxor (sbit src src-index) 1))))))))