1 ;;;; This file contains the definition of the CTYPE (Compiler TYPE)
2 ;;;; structure and related macros used for manipulating it. This is
3 ;;;; sort of a mini object system with rather odd dispatching rules.
4 ;;;; Other compile-time definitions needed by multiple files are also
7 ;;;; FIXME: The comment above about what's in this file is no longer so
8 ;;;; true now that I've split off type-class.lisp. Perhaps we should
9 ;;;; split off CTYPE into the same file as type-class.lisp, rename that
10 ;;;; file to ctype.lisp, move the current comment to the head of that file,
11 ;;;; and write a new comment for this file saying how this file holds
14 ;;;; This software is part of the SBCL system. See the README file for
15 ;;;; more information.
17 ;;;; This software is derived from the CMU CL system, which was
18 ;;;; written at Carnegie Mellon University and released into the
19 ;;;; public domain. The software is in the public domain and is
20 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
21 ;;;; files for more information.
23 (in-package "SB!KERNEL")
25 (!begin-collecting-cold-init-forms
)
27 ;;; Define the translation from a type-specifier to a type structure for
28 ;;; some particular type. Syntax is identical to DEFTYPE.
29 ;;; Semantics are slightly different though: DEFTYPE causes the default
30 ;;; for missing &OPTIONAL arguments to be '* but a translator requires
31 ;;; an explicit default of '*, or else it assumes a default of NIL.
32 (defmacro !def-type-translator
(name arglist
&body body
)
33 (declare (type symbol name
))
34 (multiple-value-bind (fun arglist
)
35 (make-macro-lambda (format nil
"~A-TYPE-PARSE" name
)
36 arglist body nil nil
:environment nil
)
40 (setf (%simple-fun-arglist
(the simple-fun fun
)) ',arglist
)
41 (setf (info :type
:translator
',name
) fun
)))))
44 (defun ctype-random (mask)
45 (logand (setq *ctype-lcg-state
*
46 (logand #x8fffff
(+ (* 1103515245 *ctype-lcg-state
*) 12345)))
49 ;;; the base class for the internal representation of types
51 ;; Each CTYPE instance (incl. subtypes thereof) has a random opaque hash value.
52 ;; Hashes are mixed together to form a lookup key in the memoization wrappers
53 ;; for most operations in CTYPES. This works because CTYPEs are immutable.
54 ;; But 2 bits are "stolen" from the hash to use as flag bits.
55 ;; The sign bit indicates that the object is the *only* object representing
56 ;; its type-specifier - it is an "interned" object.
57 ;; The next highest bit indicates that the object, if compared for TYPE=
58 ;; against an interned object can quickly return false when not EQ.
59 ;; Complicated types don't admit the quick failure check.
60 ;; At any rate, the totally opaque pseudo-random bits are under this mask.
61 (defconstant +ctype-hash-mask
+
62 (ldb (byte (1- sb
!vm
:n-positive-fixnum-bits
) 0) -
1))
64 (def!struct
(ctype (:conc-name type-
)
66 (:make-load-form-fun make-type-load-form
)
67 #-sb-xc-host
(:pure t
))
68 ;; the class of this type
70 ;; FIXME: It's unnecessarily confusing to have a structure accessor
71 ;; named TYPE-CLASS-INFO which is an accessor for the CTYPE structure
72 ;; even though the TYPE-CLASS structure also exists in the system.
73 ;; Rename this slot: TYPE-CLASS or ASSOCIATED-TYPE-CLASS or something.
74 ;; [or TYPE-VTABLE or TYPE-METHODS either of which basically equates
75 ;; a type-class with the set of things it can do, while avoiding
76 ;; ambiguity to whether it is a 'CLASS-INFO' slot in a 'TYPE'
77 ;; or an 'INFO' slot in a 'TYPE-CLASS']
78 (class-info (missing-arg) :type type-class
)
79 ;; an arbitrary hash code used in EQ-style hashing of identity
80 ;; (since EQ hashing can't be done portably)
81 ;; - in the host lisp, generate a hash value using a known, simple
82 ;; random number generator (rather than the host lisp's
83 ;; implementation of RANDOM)
84 ;; - in the target, use scrambled bits from the allocation pointer
87 #+sb-xc-host
(ctype-random +ctype-hash-mask
+)
88 #-sb-xc-host
(sb!impl
::quasi-random-address-based-hash
89 *ctype-hash-state
* +ctype-hash-mask
+)
90 :type
(signed-byte #.sb
!vm
:n-fixnum-bits
)
91 ;; FIXME: is there a better way to initialize the hash value
92 ;; and its flag bit simultaneously rather than have it
93 ;; be a read/write slot?
95 (def!method print-object
((ctype ctype
) stream
)
96 (print-unreadable-object (ctype stream
:type t
)
97 (prin1 (type-specifier ctype
) stream
)))
99 ;; Set the sign bit (the "interned" bit) of the hash-value of OBJ to 1.
100 ;; This is an indicator that the object is the unique internal representation
101 ;; of any ctype that is TYPE= to this object.
102 ;; Everything starts out assumed non-unique.
103 ;; The hash-cache logic (a/k/a memoization) tends to ignore high bits when
104 ;; creating cache keys because the mixing function is XOR and the caches
105 ;; are power-of-2 sizes. Lkewise making the low bits non-random is bad
106 ;; for cache distribution.
107 (defconstant +type-admits-type
=-optimization
+
108 (ash 1 (- sb
!vm
:n-positive-fixnum-bits
1))) ; highest bit in fixnum
109 (defun mark-ctype-interned (obj)
110 (setf (type-hash-value obj
)
111 (logior sb
!xc
:most-negative-fixnum
112 (if (eq (type-class-name (type-class-info obj
)) 'array
)
114 +type-admits-type
=-optimization
+)
115 (type-hash-value obj
)))
118 (declaim (inline type-might-contain-other-types-p
))
119 (defun type-might-contain-other-types-p (ctype)
120 (type-class-might-contain-other-types-p (type-class-info ctype
)))
122 (declaim (inline type-enumerable
))
123 (defun type-enumerable (ctype)
124 (let ((answer (type-class-enumerable-p (type-class-info ctype
))))
125 (if (functionp answer
)
126 (funcall answer ctype
)
129 ;;; Just dump it as a specifier. (We'll convert it back upon loading.)
130 (defun make-type-load-form (type)
131 (declare (type ctype type
))
132 `(specifier-type ',(type-specifier type
)))
136 ;;; Look for nice relationships for types that have nice relationships
137 ;;; only when one is a hierarchical subtype of the other.
138 (defun hierarchical-intersection2 (type1 type2
)
139 (multiple-value-bind (subtypep1 win1
) (csubtypep type1 type2
)
140 (multiple-value-bind (subtypep2 win2
) (csubtypep type2 type1
)
141 (cond (subtypep1 type1
)
143 ((and win1 win2
) *empty-type
*)
145 (defun hierarchical-union2 (type1 type2
)
146 (cond ((csubtypep type1 type2
) type2
)
147 ((csubtypep type2 type1
) type1
)
150 ;;; Hash two things (types) down to a target fixnum. In CMU CL this was an EQ
151 ;;; hash, but since it now needs to run in vanilla ANSI Common Lisp at
152 ;;; cross-compile time, it's now based on the CTYPE-HASH-VALUE field
155 ;;; FIXME: This was a macro in CMU CL, and is now an INLINE function. Is
156 ;;; it important for it to be INLINE, or could be become an ordinary
157 ;;; function without significant loss? -- WHN 19990413
158 #!-sb-fluid
(declaim (inline type-cache-hash
))
159 (declaim (ftype (function (ctype ctype
) (signed-byte #.sb
!vm
:n-fixnum-bits
))
161 (defun type-cache-hash (type1 type2
)
162 (logxor (ash (type-hash-value type1
) -
3) (type-hash-value type2
)))
164 #!-sb-fluid
(declaim (inline type-list-cache-hash
))
165 (declaim (ftype (function (list) (signed-byte #.sb
!vm
:n-fixnum-bits
))
166 type-list-cache-hash
))
167 (defun type-list-cache-hash (types)
168 (loop with res of-type
(signed-byte #.sb
!vm
:n-fixnum-bits
) = 0
170 do
(setq res
(logxor (ash res -
1) (type-hash-value type
)))
171 finally
(return res
)))
173 ;;;; cold loading initializations
175 (!defun-from-collected-cold-init-forms
!typedefs-cold-init
)