;; be a SB-PCL:CLASS under some circumstances? What goes here
;; when the LAYOUT is in fact a PCL::WRAPPER?
:type #-sb-xc sb!xc:class #+sb-xc cl:class)
- ;; The value of this slot can be
+ ;; The value of this slot can be:
;; * :UNINITIALIZED if not initialized yet;
;; * NIL if this is the up-to-date layout for a class; or
;; * T if this layout has been invalidated (by being replaced by
;; * something else (probably a list) if the class is a PCL wrapper
;; and PCL has made it invalid and made a note to itself about it
(invalid :uninitialized :type (or cons (member nil t :uninitialized)))
- ;; The layouts for all classes we inherit. If hierarchical these are
- ;; in order from most general down to (but not including) this
- ;; class.
+ ;; the layouts for all classes we inherit. If hierarchical, i.e. if
+ ;; DEPTHOID >= 0, then these are ordered by ORDER-LAYOUT-INHERITS,
+ ;; so that each inherited layout appears at its expected depth,
+ ;; i.e. at its LAYOUT-DEPTHOID value.
;;
- ;; FIXME: Couldn't this be (SIMPLE-ARRAY LAYOUT 1) instead of
- ;; SIMPLE-VECTOR?
+ ;; Remaining elements are filled by the non-hierarchical layouts or,
+ ;; if they would otherwise be empty, by copies of succeeding layouts.
(inherits #() :type simple-vector)
- ;; If inheritance is hierarchical, this is -1. If inheritance is not
+ ;; If inheritance is not hierarchical, this is -1. If inheritance is
;; hierarchical, this is the inheritance depth, i.e. (LENGTH INHERITS).
;; Note:
;; (1) This turns out to be a handy encoding for arithmetically
(declaim (ftype (function (layout sb!xc:class index simple-vector layout-depthoid))
check-layout))
(defun check-layout (layout class length inherits depthoid)
- (assert (eq (layout-class layout) class))
+ (aver (eq (layout-class layout) class))
(when (redefine-layout-warning "current" layout
"compile time" length inherits depthoid)
;; Classic CMU CL had more options here. There are several reasons
;; Attempting to register ourselves with a temporary undefined
;; class placeholder is almost certainly a programmer error. (I
;; should know, I did it.) -- WHN 19990927
- (assert (not (undefined-class-p class)))
+ (aver (not (undefined-class-p class)))
;; This assertion dates from classic CMU CL. The rationale is
;; probably that calling REGISTER-LAYOUT more than once for the
;; same LAYOUT is almost certainly a programmer error.
- (assert (not (eq class-layout layout)))
+ (aver (not (eq class-layout layout)))
;; Figure out what classes are affected by the change, and issue
;; appropriate warnings and invalidations.
(values))
); EVAL-WHEN
+
+;;; Arrange the inherited layouts to appear at their expected depth,
+;;; ensuring that hierarchical type tests succeed. Layouts with
+;;; DEPTHOID >= 0 (i.e. hierarchical classes) are placed first,
+;;; at exactly that index in the INHERITS vector. Then, non-hierarchical
+;;; layouts are placed in remaining elements. Then, any still-empty
+;;; elements are filled with their successors, ensuring that each
+;;; element contains a valid layout.
+;;;
+;;; This reordering may destroy CPL ordering, so the inherits should
+;;; not be read as being in CPL order.
+(defun order-layout-inherits (layouts)
+ (declare (simple-vector layouts))
+ (let ((length (length layouts))
+ (max-depth -1))
+ (dotimes (i length)
+ (let ((depth (layout-depthoid (svref layouts i))))
+ (when (> depth max-depth)
+ (setf max-depth depth))))
+ (let* ((new-length (max (1+ max-depth) length))
+ (inherits (make-array new-length)))
+ (dotimes (i length)
+ (let* ((layout (svref layouts i))
+ (depth (layout-depthoid layout)))
+ (unless (eql depth -1)
+ (let ((old-layout (svref inherits depth)))
+ (unless (or (eql old-layout 0) (eq old-layout layout))
+ (error "layout depth conflict: ~S~%" layouts)))
+ (setf (svref inherits depth) layout))))
+ (do ((i 0 (1+ i))
+ (j 0))
+ ((>= i length))
+ (declare (type index i j))
+ (let* ((layout (svref layouts i))
+ (depth (layout-depthoid layout)))
+ (when (eql depth -1)
+ (loop (when (eql (svref inherits j) 0)
+ (return))
+ (incf j))
+ (setf (svref inherits j) layout))))
+ (do ((i (1- new-length) (1- i)))
+ ((< i 0))
+ (declare (type fixnum i))
+ (when (eql (svref inherits i) 0)
+ (setf (svref inherits i) (svref inherits (1+ i)))))
+ inherits)))
\f
+;;;; class precedence lists
+
+;;; Topologically sort the list of objects to meet a set of ordering
+;;; constraints given by pairs (A . B) constraining A to precede B.
+;;; When there are multiple objects to choose, the tie-breaker
+;;; function is called with both the list of object to choose from and
+;;; the reverse ordering built so far.
+(defun topological-sort (objects constraints tie-breaker)
+ (declare (list objects constraints)
+ (function tie-breaker))
+ (let ((obj-info (make-hash-table :size (length objects)))
+ (free-objs nil)
+ (result nil))
+ (dolist (constraint constraints)
+ (let ((obj1 (car constraint))
+ (obj2 (cdr constraint)))
+ (let ((info2 (gethash obj2 obj-info)))
+ (if info2
+ (incf (first info2))
+ (setf (gethash obj2 obj-info) (list 1))))
+ (let ((info1 (gethash obj1 obj-info)))
+ (if info1
+ (push obj2 (rest info1))
+ (setf (gethash obj1 obj-info) (list 0 obj2))))))
+ (dolist (obj objects)
+ (let ((info (gethash obj obj-info)))
+ (when (or (not info) (zerop (first info)))
+ (push obj free-objs))))
+ (loop
+ (flet ((next-result (obj)
+ (push obj result)
+ (dolist (successor (rest (gethash obj obj-info)))
+ (let* ((successor-info (gethash successor obj-info))
+ (count (1- (first successor-info))))
+ (setf (first successor-info) count)
+ (when (zerop count)
+ (push successor free-objs))))))
+ (cond ((endp free-objs)
+ (dohash (obj info obj-info)
+ (unless (zerop (first info))
+ (error "Topological sort failed due to constraint on ~S."
+ obj)))
+ (return (nreverse result)))
+ ((endp (rest free-objs))
+ (next-result (pop free-objs)))
+ (t
+ (let ((obj (funcall tie-breaker free-objs result)))
+ (setf free-objs (remove obj free-objs))
+ (next-result obj))))))))
+
+
+;;; standard class precedence list computation
+(defun std-compute-class-precedence-list (class)
+ (let ((classes nil)
+ (constraints nil))
+ (labels ((note-class (class)
+ (unless (member class classes)
+ (push class classes)
+ (let ((superclasses (class-direct-superclasses class)))
+ (do ((prev class)
+ (rest superclasses (rest rest)))
+ ((endp rest))
+ (let ((next (first rest)))
+ (push (cons prev next) constraints)
+ (setf prev next)))
+ (dolist (class superclasses)
+ (note-class class)))))
+ (std-cpl-tie-breaker (free-classes rev-cpl)
+ (dolist (class rev-cpl (first free-classes))
+ (let* ((superclasses (class-direct-superclasses class))
+ (intersection (intersection free-classes
+ superclasses)))
+ (when intersection
+ (return (first intersection)))))))
+ (note-class class)
+ (topological-sort classes constraints #'std-cpl-tie-breaker))))
+\f
+;;;; object types to represent classes
+
;;; An UNDEFINED-CLASS is a cookie we make up to stick in forward
;;; referenced layouts. Users should never see them.
(def!struct (undefined-class (:include #-sb-xc sb!xc:class
;;; the two classes are equal, since there are EQ checks in those
;;; operations.
(!define-type-method (sb!xc:class :simple-=) (type1 type2)
- (assert (not (eq type1 type2)))
+ (aver (not (eq type1 type2)))
(values nil t))
(!define-type-method (sb!xc:class :simple-subtypep) (class1 class2)
- (assert (not (eq class1 class2)))
+ (aver (not (eq class1 class2)))
(let ((subclasses (class-subclasses class2)))
(if (and subclasses (gethash class1 subclasses))
(values t t)
(system-area-pointer :codes (#.sb!vm:sap-type))
(weak-pointer :codes (#.sb!vm:weak-pointer-type))
(code-component :codes (#.sb!vm:code-header-type))
- #!-gengc (lra :codes (#.sb!vm:return-pc-header-type))
+ (lra :codes (#.sb!vm:return-pc-header-type))
(fdefn :codes (#.sb!vm:fdefn-type))
(random-class) ; used for unknown type codes
(function
- :codes (#.sb!vm:byte-code-closure-type
- #.sb!vm:byte-code-function-type
- #.sb!vm:closure-header-type
+ :codes (#.sb!vm:closure-header-type
#.sb!vm:function-header-type)
:state :read-only)
(funcallable-instance
generic-number)
:codes (#.sb!vm:bignum-type))
(stream
- :hierarchical-p nil
:state :read-only
- :inherits (instance t)))))
+ :depth 3
+ :inherits (instance)))))
;;; comment from CMU CL:
;;; See also type-init.lisp where we finish setting up the
codes
enumerable
state
+ depth
(hierarchical-p t) ; might be modified below
(direct-superclasses (if inherits
(list (car inherits))
'(t))))
x
(declare (ignore codes state translation))
- (let ((inherits-list (if (eq name 't)
- ()
- (cons 't (reverse inherits))))
+ (let ((inherits-list (if (eq name t)
+ ()
+ (cons t (reverse inherits))))
(class (make-built-in-class
:enumerable enumerable
:name name
:translation (if trans-p :initializing nil)
:direct-superclasses
- (if (eq name 't)
+ (if (eq name t)
nil
(mapcar #'sb!xc:find-class direct-superclasses)))))
(setf (info :type :kind name) :primitive
(unless trans-p
(setf (info :type :builtin name) class))
(let* ((inherits-vector
- (map 'vector
+ (map 'simple-vector
(lambda (x)
(let ((super-layout
(class-layout (sb!xc:find-class x))))
(setf hierarchical-p nil))
super-layout))
inherits-list))
- (depthoid (if hierarchical-p (length inherits-vector) -1)))
+ (depthoid (if hierarchical-p
+ (or depth (length inherits-vector))
+ -1)))
(register-layout
(find-and-init-or-check-layout name
0
;;; is loaded and the class defined.
(!cold-init-forms
(/show0 "about to define temporary STANDARD-CLASSes")
- (dolist (x '((fundamental-stream (t instance stream))))
+ (dolist (x '(;; Why is STREAM duplicated in this list? Because, when
+ ;; the inherits-vector of FUNDAMENTAL-STREAM is set up,
+ ;; a vector containing the elements of the list below,
+ ;; i.e. '(T INSTANCE STREAM STREAM), is created, and
+ ;; this is what the function ORDER-LAYOUT-INHERITS
+ ;; would do, too.
+ ;;
+ ;; So, the purpose is to guarantee a valid layout for
+ ;; the FUNDAMENTAL-STREAM class, matching what
+ ;; ORDER-LAYOUT-INHERITS would do.
+ ;; ORDER-LAYOUT-INHERITS would place STREAM at index 3
+ ;; in the INHERITS(-VECTOR). Index 2 would not be
+ ;; filled, so STREAM is duplicated there (as
+ ;; ORDER-LAYOUTS-INHERITS would do). Maybe the
+ ;; duplicate definition could be removed (removing a
+ ;; STREAM element), because FUNDAMENTAL-STREAM is
+ ;; redefined after PCL is set up, anyway. But to play
+ ;; it safely, we define the class with a valid INHERITS
+ ;; vector.
+ (fundamental-stream (t instance stream stream))))
(/show0 "defining temporary STANDARD-CLASS")
(let* ((name (first x))
(inherits-list (second x))
(setf (class-cell-class class-cell) class
(info :type :class name) class-cell
(info :type :kind name) :instance)
- (let ((inherits (map 'vector
+ (let ((inherits (map 'simple-vector
(lambda (x)
(class-layout (sb!xc:find-class x)))
inherits-list)))
projects / sbcl.git / blobdiff