X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Fclass.lisp;h=4b87df7b57f64af035b313097192d7fabd8acc12;hb=3c65762b927af861c9c8bc416e4cbac9a14ec0c3;hp=fda5bedbc61dc4da243a1715d66628e9c02a84ff;hpb=a8fa26a6e9804d3548f5bca9361a91345a689099;p=sbcl.git diff --git a/src/code/class.lisp b/src/code/class.lisp index fda5bed..4b87df7 100644 --- a/src/code/class.lisp +++ b/src/code/class.lisp @@ -180,7 +180,7 @@ ;; 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 @@ -188,14 +188,15 @@ ;; * 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 @@ -514,7 +515,132 @@ (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))) +;;;; 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)))) + +;;;; 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 @@ -788,23 +914,21 @@ (character :enumerable t :translation base-char) (base-char :enumerable t :inherits (character) - :codes (#.sb!vm:base-char-type)) - (symbol :codes (#.sb!vm:symbol-header-type)) + :codes (#.sb!vm:base-char-widetag)) + (symbol :codes (#.sb!vm:symbol-header-widetag)) (instance :state :read-only) - (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)) - (fdefn :codes (#.sb!vm:fdefn-type)) + (system-area-pointer :codes (#.sb!vm:sap-widetag)) + (weak-pointer :codes (#.sb!vm:weak-pointer-widetag)) + (code-component :codes (#.sb!vm:code-header-widetag)) + (lra :codes (#.sb!vm:return-pc-header-widetag)) + (fdefn :codes (#.sb!vm:fdefn-widetag)) (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 - #.sb!vm:function-header-type) + :codes (#.sb!vm:closure-header-widetag + #.sb!vm:simple-fun-header-widetag) :state :read-only) (funcallable-instance :inherits (function) @@ -832,11 +956,11 @@ :inherits (generic-array mutable-sequence mutable-collection generic-sequence collection)) - (array :translation array :codes (#.sb!vm:complex-array-type) + (array :translation array :codes (#.sb!vm:complex-array-widetag) :inherits (generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array - :translation simple-array :codes (#.sb!vm:simple-array-type) + :translation simple-array :codes (#.sb!vm:simple-array-widetag) :inherits (array generic-array mutable-sequence mutable-collection generic-sequence collection)) (sequence @@ -844,25 +968,25 @@ :inherits (mutable-sequence mutable-collection generic-sequence collection)) (vector - :translation vector :codes (#.sb!vm:complex-vector-type) + :translation vector :codes (#.sb!vm:complex-vector-widetag) :direct-superclasses (array sequence generic-vector) :inherits (array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-vector - :translation simple-vector :codes (#.sb!vm:simple-vector-type) + :translation simple-vector :codes (#.sb!vm:simple-vector-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (bit-vector - :translation bit-vector :codes (#.sb!vm:complex-bit-vector-type) + :translation bit-vector :codes (#.sb!vm:complex-bit-vector-widetag) :inherits (vector array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-bit-vector - :translation simple-bit-vector :codes (#.sb!vm:simple-bit-vector-type) + :translation simple-bit-vector :codes (#.sb!vm:simple-bit-vector-widetag) :direct-superclasses (bit-vector simple-array) :inherits (bit-vector vector simple-array array sequence @@ -870,77 +994,77 @@ mutable-collection generic-sequence collection)) (simple-array-unsigned-byte-2 :translation (simple-array (unsigned-byte 2) (*)) - :codes (#.sb!vm:simple-array-unsigned-byte-2-type) + :codes (#.sb!vm:simple-array-unsigned-byte-2-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-unsigned-byte-4 :translation (simple-array (unsigned-byte 4) (*)) - :codes (#.sb!vm:simple-array-unsigned-byte-4-type) + :codes (#.sb!vm:simple-array-unsigned-byte-4-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-unsigned-byte-8 :translation (simple-array (unsigned-byte 8) (*)) - :codes (#.sb!vm:simple-array-unsigned-byte-8-type) + :codes (#.sb!vm:simple-array-unsigned-byte-8-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-unsigned-byte-16 :translation (simple-array (unsigned-byte 16) (*)) - :codes (#.sb!vm:simple-array-unsigned-byte-16-type) + :codes (#.sb!vm:simple-array-unsigned-byte-16-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-unsigned-byte-32 :translation (simple-array (unsigned-byte 32) (*)) - :codes (#.sb!vm:simple-array-unsigned-byte-32-type) + :codes (#.sb!vm:simple-array-unsigned-byte-32-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-signed-byte-8 :translation (simple-array (signed-byte 8) (*)) - :codes (#.sb!vm:simple-array-signed-byte-8-type) + :codes (#.sb!vm:simple-array-signed-byte-8-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-signed-byte-16 :translation (simple-array (signed-byte 16) (*)) - :codes (#.sb!vm:simple-array-signed-byte-16-type) + :codes (#.sb!vm:simple-array-signed-byte-16-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-signed-byte-30 :translation (simple-array (signed-byte 30) (*)) - :codes (#.sb!vm:simple-array-signed-byte-30-type) + :codes (#.sb!vm:simple-array-signed-byte-30-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-signed-byte-32 :translation (simple-array (signed-byte 32) (*)) - :codes (#.sb!vm:simple-array-signed-byte-32-type) + :codes (#.sb!vm:simple-array-signed-byte-32-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-single-float :translation (simple-array single-float (*)) - :codes (#.sb!vm:simple-array-single-float-type) + :codes (#.sb!vm:simple-array-single-float-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-double-float :translation (simple-array double-float (*)) - :codes (#.sb!vm:simple-array-double-float-type) + :codes (#.sb!vm:simple-array-double-float-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence @@ -948,21 +1072,21 @@ #!+long-float (simple-array-long-float :translation (simple-array long-float (*)) - :codes (#.sb!vm:simple-array-long-float-type) + :codes (#.sb!vm:simple-array-long-float-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-complex-single-float :translation (simple-array (complex single-float) (*)) - :codes (#.sb!vm:simple-array-complex-single-float-type) + :codes (#.sb!vm:simple-array-complex-single-float-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence mutable-collection generic-sequence collection)) (simple-array-complex-double-float :translation (simple-array (complex double-float) (*)) - :codes (#.sb!vm:simple-array-complex-double-float-type) + :codes (#.sb!vm:simple-array-complex-double-float-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence @@ -970,7 +1094,7 @@ #!+long-float (simple-array-complex-long-float :translation (simple-array (complex long-float) (*)) - :codes (#.sb!vm:simple-array-complex-long-float-type) + :codes (#.sb!vm:simple-array-complex-long-float-widetag) :direct-superclasses (vector simple-array) :inherits (vector simple-array array sequence generic-vector generic-array mutable-sequence @@ -981,7 +1105,7 @@ collection)) (string :translation string - :codes (#.sb!vm:complex-string-type) + :codes (#.sb!vm:complex-string-widetag) :direct-superclasses (vector generic-string) :inherits (vector array sequence generic-vector generic-array generic-string @@ -989,7 +1113,7 @@ generic-sequence collection)) (simple-string :translation simple-string - :codes (#.sb!vm:simple-string-type) + :codes (#.sb!vm:simple-string-widetag) :direct-superclasses (string simple-array) :inherits (string vector simple-array array sequence @@ -1000,7 +1124,7 @@ :inherits (sequence mutable-sequence mutable-collection generic-sequence collection)) (cons - :codes (#.sb!vm:list-pointer-type) + :codes (#.sb!vm:list-pointer-lowtag) :translation cons :inherits (list sequence mutable-sequence mutable-collection @@ -1016,20 +1140,20 @@ (complex :translation complex :inherits (number generic-number) - :codes (#.sb!vm:complex-type)) + :codes (#.sb!vm:complex-widetag)) (complex-single-float :translation (complex single-float) :inherits (complex number generic-number) - :codes (#.sb!vm:complex-single-float-type)) + :codes (#.sb!vm:complex-single-float-widetag)) (complex-double-float :translation (complex double-float) :inherits (complex number generic-number) - :codes (#.sb!vm:complex-double-float-type)) + :codes (#.sb!vm:complex-double-float-widetag)) #!+long-float (complex-long-float :translation (complex long-float) :inherits (complex number generic-number) - :codes (#.sb!vm:complex-long-float-type)) + :codes (#.sb!vm:complex-long-float-widetag)) (real :translation real :inherits (number generic-number)) (float :translation float @@ -1037,23 +1161,23 @@ (single-float :translation single-float :inherits (float real number generic-number) - :codes (#.sb!vm:single-float-type)) + :codes (#.sb!vm:single-float-widetag)) (double-float :translation double-float :inherits (float real number generic-number) - :codes (#.sb!vm:double-float-type)) + :codes (#.sb!vm:double-float-widetag)) #!+long-float (long-float :translation long-float :inherits (float real number generic-number) - :codes (#.sb!vm:long-float-type)) + :codes (#.sb!vm:long-float-widetag)) (rational :translation rational :inherits (real number generic-number)) (ratio :translation (and rational (not integer)) :inherits (rational real number generic-number) - :codes (#.sb!vm:ratio-type)) + :codes (#.sb!vm:ratio-widetag)) (integer :translation integer :inherits (rational real number generic-number)) @@ -1062,16 +1186,16 @@ #.sb!vm:*target-most-positive-fixnum*) :inherits (integer rational real number generic-number) - :codes (#.sb!vm:even-fixnum-type #.sb!vm:odd-fixnum-type)) + :codes (#.sb!vm:even-fixnum-lowtag #.sb!vm:odd-fixnum-lowtag)) (bignum :translation (and integer (not fixnum)) :inherits (integer rational real number generic-number) - :codes (#.sb!vm:bignum-type)) + :codes (#.sb!vm:bignum-widetag)) (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 @@ -1086,6 +1210,7 @@ codes enumerable state + depth (hierarchical-p t) ; might be modified below (direct-superclasses (if inherits (list (car inherits)) @@ -1108,7 +1233,7 @@ (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)))) @@ -1116,7 +1241,9 @@ (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 @@ -1130,7 +1257,26 @@ ;;; 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)) @@ -1139,7 +1285,7 @@ (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)))