| blob | 22df70982e633194ad45167395fad11d8d858d2e |
1 ;;;; This file provides a functional interface to global information
2 ;;;; about named things in the system. Information is considered to be
3 ;;;; global if it must persist between invocations of the compiler. The
4 ;;;; use of a functional interface eliminates the need for the compiler
5 ;;;; to worry about the actual representation. This is important, since
6 ;;;; the information may well have several representations.
7 ;;;;
8 ;;;; The database contains arbitrary Lisp values, addressed by a
9 ;;;; combination of Name, Class and Type. The Name is an EQUAL-thing
10 ;;;; which is the name of the thing we are recording information
11 ;;;; about. Class is the kind of object involved. Typical classes are
12 ;;;; :FUNCTION, :VARIABLE, :TYPE, ... A Type names a particular piece
13 ;;;; of information within a given class. Class and Type are keywords,
14 ;;;; and are compared with EQ.
16 ;;;; The relation between this file and 'info-vectors' is that the
17 ;;;; latter provides a fundamental mechanism to create property-list-like
18 ;;;; things whose "indicators" are restricted to small integers
19 ;;;; and whose values are anything; whereas the globaldb provides the
20 ;;;; facility of looking up the properties by keyword, a/k/a Class+Type.
21 ;;;; The keyword regime is somewhat arbitrary because ultimately the
22 ;;;; pair of keywords just translates to a small integer, usually
23 ;;;; resolvable at compile-time for the most part.
25 ;;;; This software is part of the SBCL system. See the README file for
26 ;;;; more information.
27 ;;;;
28 ;;;; This software is derived from the CMU CL system, which was
29 ;;;; written at Carnegie Mellon University and released into the
30 ;;;; public domain. The software is in the public domain and is
31 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
32 ;;;; files for more information.
39 ;;; The DEFVAR for this appears later.
40 ;;; FIXME: centralize
43 ;;; This is sorta semantically equivalent to SXHASH, but better-behaved for
44 ;;; legal function names. It performs more work by not cutting off as soon
45 ;;; in the CDR direction, thereby improving the distribution of method names.
46 ;;; More work here equates to less work in the global hashtable.
47 ;;; To wit: (eq (sxhash '(foo a b c bar)) (sxhash '(foo a b c d))) => T
48 ;;; but the corresponding globaldb-sxhashoids differ.
49 ;;; This is no longer inline because for the cases where it is needed -
50 ;;; names which are not just symbols or (SETF F) - an extra call has no impact.
52 ;; we can't use MIX because it's in 'target-sxhash',
53 ;; so use the host's sxhash, but ensure that the result is a target fixnum.
55 #-sb-xc-host
58 ;; TRAVERSE will walk across more cons cells than RECURSE will descend.
59 ;; That's why this isn't just one self-recursive function.
74 ;;; Given any non-negative integer, return a prime number >= to it.
75 ;;;
76 ;;; FIXME: This logic should be shared with ALMOST-PRIMIFY in
77 ;;; hash-table.lisp. Perhaps the merged logic should be
78 ;;; PRIMIFY-HASH-TABLE-SIZE, implemented as a lookup table of primes
79 ;;; after integral powers of two:
80 ;;; #(17 37 67 131 ..)
81 ;;; (Or, if that's too coarse, after half-integral powers of two.) By
82 ;;; thus getting rid of any need for primality testing at runtime, we
83 ;;; could punt POSITIVE-PRIMEP, too.
88 \f
89 ;;;; info classes, info types, and type numbers, part I: what's needed
90 ;;;; not only at compile time but also at run time
92 ;;;; Note: This section is a blast from the past, a little trip down
93 ;;;; memory lane to revisit the weird host/target interactions of the
94 ;;;; CMU CL build process. Because of the way that the cross-compiler
95 ;;;; and target compiler share stuff here, if you change anything in
96 ;;;; here, you'd be well-advised to nuke all your fasl files and
97 ;;;; restart compilation from the very beginning of the bootstrap
98 ;;;; process.
100 ;;; Why do we suppress the :COMPILE-TOPLEVEL situation here when we're
101 ;;; running the cross-compiler? The cross-compiler (which was built
102 ;;; from these sources) has its version of these data and functions
103 ;;; defined in the same places we'd be defining into. We're happy with
104 ;;; its version, since it was compiled from the same sources, so
105 ;;; there's no point in overwriting its nice compiled version of this
106 ;;; stuff with our interpreted version. (And any time we're *not*
107 ;;; happy with its version, perhaps because we've been editing the
108 ;;; sources partway through bootstrapping, tch tch, overwriting its
109 ;;; version with our version would be unlikely to help, because that
110 ;;; would make the cross-compiler very confused.)
113 ;;; a map from type numbers to TYPE-INFO objects. There is one type
114 ;;; number for each defined CLASS/TYPE pair.
115 ;;;
116 ;;; We build its value at build-the-cross-compiler time (with calls to
117 ;;; DEFINE-INFO-TYPE), then generate code to recreate the compile time
118 ;;; value, and arrange for that code to be called in cold load.
119 ;;; KLUDGE: We don't try to reset its value when cross-compiling the
120 ;;; compiler, since that creates too many bootstrapping problems,
121 ;;; instead just reusing the built-in-the-cross-compiler version,
122 ;;; which is theoretically a little bit ugly but pretty safe in
123 ;;; practice because the cross-compiler is as close to the target
124 ;;; compiler as we can make it, i.e. identical in most ways, including
125 ;;; this one. -- WHN 2001-08-19
130 #-no-ansi-print-object
134 "~S ~S, Number = ~W"
138 (:constructor
141 ;; the name of this type
143 ;; this type's class
145 ;; a number that uniquely identifies this type (and implicitly its class)
147 ;; a type specifier which info of this type must satisfy
149 ;; If FUNCTIONP, then a function called when there is no information of
150 ;; this type. If not FUNCTIONP, then any object serving as a default.
152 ;; Two functions called by (SETF INFO) before calling SET-INFO-VALUE.
153 ;; Regarding the type specifiers on these slots, I wanted to write them
154 ;; as (SFUNCTION (T) T) for documentation - and it elides the check for
155 ;; multiple values returned - but doing that causes failure building the
156 ;; cross-compiler under CMUCL 20c because it tries to call TYPEP on that,
157 ;; and complains that it can't.
158 ;; 1. A function that type-checks its argument and returns it,
159 ;; or signals an error.
161 ;; 2. a function of two arguments, a name and new-value, which performs
162 ;; any other checks and/or side-effects including signaling an error.
168 ;; Perform the equivalent of (GET-INFO-VALUE sym +INFO-METAINFO-TYPE-NUM+)
169 ;; but without the AVER that metadata already exists, and bypassing the
170 ;; defaulting logic.
178 ;; Find or create a TYPE-INFO object designated by CLASS- and TYPE-KEYWORD.
179 ;; If not found, the specified TYPE-NUM and TYPE-SPEC are used to
180 ;; initialize it. If TYPE-NUM is -1, the next available number is assigned.
181 ;; Return the new type-num.
187 ;; The zeroth type-num is reserved for INFO's own private use.
188 ;; +fdefn-type-num+ is also reserved and must be special-cased.
189 ;; Generalizing DEFINE-INFO-TYPE to optionally pass a type-number
190 ;; would also mean changing the fact that a specified number is
191 ;; used only for restoring *INFO-TYPES* during cold-init.
199 type-num class-keyword type-keyword type-spec)
209 ;; If CLASS-KEYWORD/TYPE-KEYWORD designate an info-type,
210 ;; return the corresponding TYPE-INFO object, otherwise NIL.
214 ;; Most TYPE-KEYWORDs uniquely designate an object, so we store only that.
215 ;; Otherwise we store a list which has a small handful of (<= 4) items.
217 ;; Can we *please* make (FIND ...) not call GENERIC+
218 ;; so that I don't feel compelled to express this as a DOLIST ?
221 class-keyword)
224 metadata))))
235 \f
236 ;;;; info types, and type numbers, part II: what's
237 ;;;; needed only at compile time, not at run time
241 ;;; a list of forms for initializing the DEFAULT slots of TYPE-INFO
242 ;;; objects, accumulated during compilation and eventually converted
243 ;;; into a function to be called at cold load time after the
244 ;;; appropriate TYPE-INFO objects have been created
245 ;;;
246 ;;; Note: This is quite similar to the !COLD-INIT-FORMS machinery, but
247 ;;; we can't conveniently use the ordinary !COLD-INIT-FORMS machinery
248 ;;; here. The problem is that the natural order in which the
249 ;;; default-slot-initialization forms are generated relative to the
250 ;;; order in which the TYPE-INFO-creation forms are generated doesn't
251 ;;; match the relative order in which the forms need to be executed at
252 ;;; cold load time.
255 ;;; Define a new type of global information.
256 ;;; CLASS/TYPE form a two-piece name for the kind of information,
257 ;;; DEFAULT is a defaulting expression, and TYPE-SPEC
258 ;;; is a type specifier which values of the type must satisfy.
259 ;;; Roughly speaking there is a hierarchy to the two-piece names
260 ;;; but this is a fiction that is not maintained anywhere in the internals.
261 ;;;
262 ;;; If the defaulting expression's value is a function, it is called with
263 ;;; the name for which the information is being looked up; otherwise it is
264 ;;; taken as the default value. The defaulting expression is used each time
265 ;;; a value is needed when one hasn't been previously set. (The result
266 ;;; does not automatically become the new value for the piece of info.)
267 ;;; Should a default value be itself a function, this must be expressed as
268 ;;; :DEFAULT (CONSTANTLY #'<a-function-name>) to adhere to the convention
269 ;;; that default objects satisfying FUNCTIONP will always be funcalled.
270 ;;;
271 ;;; The main thing we do is determine the type's number. We need to do
272 ;;; this at macroexpansion time, since both the COMPILE and LOAD time
273 ;;; calls to %DEFINE-INFO-TYPE must use the same type number.
274 (#+sb-xc-host defmacro
279 default)
283 ;; At compile time, ensure that the type number exists. It will
284 ;; need to be forced to exist at cold load time, too, but
285 ;; that's not handled here; it's handled by later code which
286 ;; looks at the compile time state and generates code to
287 ;; replicate it at cold load time.
289 ;; Arrange for TYPE-INFO-DEFAULT, TYPE-INFO-TYPE-CHECKER, and
290 ;; TYPE-INFO-VALIDATE-FUNCTION to be set at cold load
291 ;; time. (They can't very well be set at cross-compile time,
292 ;; since they differ between host and target and are
293 ;; host-compiled closures.)
295 ;; cold-init can't actually AVER without crashing hard,
296 ;; but what the heck, let's do it.
299 ;; avoid re-inventing #'IDENTITY N times over
303 ,',validate-function
309 \f
311 ;;; INFO is the standard way to access the database. It's settable.
312 ;;;
313 ;;; Return the information of the specified TYPE and CLASS for NAME.
314 ;;; The second value returned is true if there is any such information
315 ;;; recorded. If there is no information, the first value returned is
316 ;;; the default and the second value returned is NIL.
328 ;;; Clear the information of the specified TYPE and CLASS for NAME in
329 ;;; the current environment. Return true if there was any info.
336 ;; A call to UNCROSS was suspiciously absent, so I added this ERROR
337 ;; to be certain that it's not supposed to happen when building the xc.
341 :simple
342 ;; If PACKED-INFO-REMOVE has nothing to do, it returns NIL,
343 ;; corresponding to the input that UPDATE-SYMBOL-INFO expects.
347 :hairy
348 ;; The global hashtable is not imbued with knowledge of the convention
349 ;; for PACKED-INFO-REMOVE because that would render it less useful
350 ;; as a general-purpose global hashtable for other kinds of stuff
351 ;; that I might want it to store aside from packed infos.
352 ;; So here UPDATE might receive NIL but must not return NIL if
353 ;; there was a non-nil input. NIL doesn't mean "do nothing".
356 ;; if -REMOVE => nil, then update NEW but return OLD
359 old))))
363 ;;;; *INFO-ENVIRONMENT*
365 (!cold-init-forms
369 ;;;; GET-INFO-VALUE
371 ;;; Return the value of NAME / TYPE-NUMBER from the global environment,
372 ;;; or return the default if there is no global info.
373 ;;; The secondary value indicates whether info was found vs defaulted.
375 get-info-value))
377 ;; sanity check: If we have screwed up initialization somehow, then
378 ;; *INFO-TYPES* could still be uninitialized at the time we try to
379 ;; get an info value, and then we'd be out of luck. (This happened,
380 ;; and was confusing to debug, when rewriting EVAL-WHEN in
381 ;; sbcl-0.pre7.x.)
398 ;; Perform the approximate equivalent operations of retrieving
399 ;; (INFO :CLASS :TYPE NAME), but if no info is found, invoke CREATION-FORM
400 ;; to produce an object that becomes the value for that piece of info, storing
401 ;; and returning it. The entire sequence behaves atomically but with a proviso:
402 ;; the creation form's result may be discarded, and another object returned
403 ;; instead (presumably) from another thread's execution of the creation form.
404 ;; If constructing the object has either non-trivial cost, or deleterious
405 ;; side-effects from making and discarding its result, do NOT use this macro.
406 ;; A mutex-guarded table would probably be more appropriate in such cases.
407 ;;
418 ;; Call FUNCTION once for each Name in globaldb that has information associated
419 ;; with it, passing the function the Name as its only argument.
420 ;;
429 ;; Check whether SYMBOL has info for itself
432 ;; Now deal with (<othersym> SYMBOL) names
441 \f
442 ;;;; ":FUNCTION" subsection - Data pertaining to globally known functions.
444 ;; must be info type number 1
450 ;;; the kind of functional object being described. If null, NAME isn't
451 ;;; a known functional object.
454 ;; I'm a little confused what the correct behavior of this default
455 ;; is. It's not clear how to generalize the FBOUNDP expression to
456 ;; the cross-compiler. As far as I can tell, NIL is a safe default
457 ;; -- it might keep the compiler from making some valid
458 ;; optimization, but it shouldn't produce incorrect code. -- WHN
459 ;; 19990330
460 :default
461 #+sb-xc-host nil
464 ;;; The type specifier for this function.
466 :type-spec ctype
467 ;; Again (as in DEFINE-INFO-TYPE :CLASS :FUNCTION :TYPE :KIND) it's
468 ;; not clear how to generalize the FBOUNDP expression to the
469 ;; cross-compiler. -- WHN 19990330
470 :default
471 ;; Delay evaluation of (SPECIFIER-TYPE) since it can't work yet
479 ;;; the ASSUMED-TYPE for this function, if we have to infer the type
480 ;;; due to not having a declaration or definition
482 ;; FIXME: The type-spec really should be
483 ;; (or approximate-fun-type null)).
484 ;; It was changed to T as a hopefully-temporary hack while getting
485 ;; cold init problems untangled.
488 ;;; where this information came from:
489 ;;; :ASSUMED = from uses of the object
490 ;;; :DEFINED = from examination of the definition
491 ;;; :DEFINED-METHOD = implicit, incremental declaration by CLOS.
492 ;;; :DECLARED = from a declaration
493 ;;; :DEFINED trumps :ASSUMED, :DEFINED-METHOD trumps :DEFINED,
494 ;;; and :DECLARED trumps :DEFINED-METHOD.
495 ;;; :DEFINED and :ASSUMED are useful for issuing compile-time warnings,
496 ;;; :DEFINED-METHOD and :DECLARED are useful for ANSIly specializing
497 ;;; code which implements the function, or which uses the function's
498 ;;; return values.
501 :default
502 ;; Again (as in DEFINE-INFO-TYPE :CLASS :FUNCTION :TYPE :KIND) it's
503 ;; not clear how to generalize the FBOUNDP expression to the
504 ;; cross-compiler. -- WHN 19990606
508 ;;; something which can be decoded into the inline expansion of the
509 ;;; function, or NIL if there is none
510 ;;;
511 ;;; To inline a function, we want a lambda expression, e.g.
512 ;;; '(LAMBDA (X) (+ X 1)). That can be encoded here in one of two
513 ;;; ways.
514 ;;; * The value in INFO can be the lambda expression itself, e.g.
515 ;;; (SETF (INFO :FUNCTION :INLINE-EXPANSION-DESIGNATOR 'FOO)
516 ;;; '(LAMBDA (X) (+ X 1)))
517 ;;; This is the ordinary way, the natural way of representing e.g.
518 ;;; (DECLAIM (INLINE FOO))
519 ;;; (DEFUN FOO (X) (+ X 1))
520 ;;; * The value in INFO can be a closure which returns the lambda
521 ;;; expression, e.g.
522 ;;; (SETF (INFO :FUNCTION :INLINE-EXPANSION-DESIGNATOR 'BAR-LEFT-CHILD)
523 ;;; (LAMBDA ()
524 ;;; '(LAMBDA (BAR) (BAR-REF BAR 3))))
525 ;;; This twisty way of storing values is supported in order to
526 ;;; allow structure slot accessors, and perhaps later other
527 ;;; stereotyped functions, to be represented compactly.
531 ;;; This specifies whether this function may be expanded inline. If
532 ;;; null, we don't care.
535 ;;; a macro-like function which transforms a call to this function
536 ;;; into some other Lisp form. This expansion is inhibited if inline
537 ;;; expansion is inhibited
540 ;;; the macroexpansion function for this macro
543 ;;; the compiler-macroexpansion function for this macro
547 ;;; a function which converts this special form into IR1
550 ;;; If a function is "known" to the compiler, then this is a FUN-INFO
551 ;;; structure containing the info used to special-case compilation.
556 \f
557 ;;;; ":VARIABLE" subsection - Data pertaining to globally known variables.
559 ;;; the kind of variable-like thing described
564 :constant
572 ;;; the declared type for this variable
574 :type-spec ctype
575 ;; Delay evaluation of *UNIVERSAL-TYPE* since it can't work yet
578 ;;; where this type and kind information came from
582 ;;; the macro-expansion for symbol-macros
590 ;; :WIRED-TLS describes how SYMBOL-VALUE (implicit or not) should be compiled.
591 ;; - :ALWAYS-HAS-TLS means that calls to SYMBOL-VALUE should access the TLS
592 ;; with a fixed offset. The index is assigned no later than load-time of
593 ;; the file containing code thus compiled. Presence of an index in the
594 ;; image that performed compilation is irrelevant (for now).
595 ;; - :ALWAYS-THREAD-LOCAL implies a fixed offset, *and* that the check for
596 ;; no-tls-value may be elided. There is currently no way to set this.
597 ;; Note that this does not affect elision of the check for unbound-marker
598 ;; which is under control of the :ALWAYS-BOUND info.
599 ;; - an integer is a permanent index, and also implies :ALWAYS-THREAD-LOCAL.
600 ;; Specials in the CL package (notably reader/printer controls) use a wired-tls,
601 ;; whether or not we bind per-thread [if we don't, that's a bug!]
602 ;; We don't assume wired TLS more generally, because user code often defines
603 ;; thousands of DEFVARs, possibly due to poor style, or due to ANSI's stance
604 ;; that DEFCONSTANT is only for EQL-comparable objects. In such cases with
605 ;; more symbols than can be bound per-thread, the compiler won't exacerbate
606 ;; things by making the loader eagerly assign a TLS index to every symbol
607 ;; ever referenced by SYMBOL-VALUE or SET. Depletion should occur lazily.
608 ;;
612 :default
616 #-sb-xc-host
618 #+sb-xc-host
623 ;; I'm not worried about random extra externals in some bizarro
624 ;; host lisp. TLS assignment has no bearing on semantics at all.
629 ;;;; ":TYPE" subsection - Data pertaining to globally known types.
631 ;;; the kind of type described. We return :INSTANCE for standard types
632 ;;; that are implemented as structures. For PCL classes, that have
633 ;;; only been compiled, but not loaded yet, we return
634 ;;; :FORTHCOMING-DEFCLASS-TYPE.
645 ;;; the expander function for a defined type
650 ;;; function that parses type specifiers into CTYPE structures
653 ;;; If true, then the type coresponding to this name. Note that if
654 ;;; this is a built-in class with a translation, then this is the
655 ;;; translation, not the class object. This info type keeps track of
656 ;;; various atomic types (NIL etc.) and also serves as a cache to
657 ;;; ensure that common standard types (atomic and otherwise) are only
658 ;;; consed once.
661 ;;; The classoid-cell for this type
664 ;;; layout for this type being used by the compiler
671 ;;; DEFTYPE lambda-list
676 ;;;; ":TYPED-STRUCTURE" subsection.
677 ;;;; Data pertaining to structures that used DEFSTRUCT's :TYPE option.
681 ;;;; ":DECLARATION" subsection - Data pertaining to user-defined declarations.
682 ;; CLTL2 offers an API to provide a list of known declarations, but it is
683 ;; inefficient to iterate over info environments to find all such declarations,
684 ;; and this is likely to be even slower when info is attached
685 ;; directly to symbols, as it would entail do-all-symbols or similar.
686 ;; Therefore maintain a list of recognized declarations. This list makes the
687 ;; globaldb storage of same redundant, but oh well.
690 :type-spec boolean
691 ;; There's no portable way to unproclaim that a symbol is a declaration,
692 ;; but at the low-level permit new-value to be NIL.
707 ;;;; ":ALIEN-TYPE" subsection - Data pertaining to globally known alien-types.
717 ;;;; ":SETF" subsection - Data pertaining to expansion of the omnipotent macro.
722 ;;;; ":RANDOM-DOCUMENTATION" subsection.
723 ;;; This is used for storing miscellaneous documentation types. The
724 ;;; stuff is an alist translating documentation kinds to values.
727 ;;;; ":SOURCE-LOCATION" subsection.
728 ;;; This is kind of the opposite of what I'd have thought more logical,
729 ;;; where each of the above subsections - also called "info classes" -
730 ;;; has one of its kinds of information being :SOURCE-LOCATION. And in fact
731 ;;; that *is* how :TYPE was handled. However, many global entities
732 ;;; store their source-location hanging off some other hook, avoiding the
733 ;;; globaldb entirely, such as functions using a #<code-component>.
734 ;;; So either way is basically a hodgepodge.
743 ;; This is for the SB-INTROSPECT contrib module, and debugging.
748 ;; This is for debugging at the REPL.
760 name)
762 sym)))
764 \f
765 ;;; Now that we have finished initializing
766 ;;; *INFO-TYPES* (at compile time), generate code to set them at cold
767 ;;; load time to the same state they have currently.
768 (!cold-init-forms
770 #-sb-xc-host
771 ;; Host already has this array, do not clobber it
776 when info-type
780 ;; KLUDGE: for repeatable xc fasls, to
781 ;; avoid different cross-compiler
782 ;; treatment of equal constants here we
783 ;; COPY-TREE, which is not in general a
784 ;; valid identity transformation
785 ;; [e.g. on (EQL (FOO))] but is OK for
786 ;; all the types we use here.
790 ;;; At cold load time, after the INFO-TYPE objects have been created,
791 ;;; we can set their DEFAULT and TYPE slots.
793 `(!cold-init-forms
794 ;; I [dpk] really think reversal now is a red herring.
795 ;; I see nothing that would fail here regardless of order.
798 \f
799 ;;; Source transforms / compiler macros for INFO functions.
800 ;;;
801 ;;; When building the XC, we give it a source transform, so that it can
802 ;;; compile INFO calls in the target efficiently; we also give it a compiler
803 ;;; macro, so that at least those INFO calls compiled after this file can be
804 ;;; efficient. (Host compiler-macros do not fire when compiling the target,
805 ;;; and source transforms don't fire when building the XC, so we need both.)
806 ;;;
807 ;;; Target needs just one, since there compiler macros and source-transforms
808 ;;; are equivalent.
813 #+sb-xc-host
816 ,form
820 ,form
821 .whole.)))))
838 ;; is (or ... null), but non-null in host implies non-null
844 ;; enforce type-correctness regardless of enclosing policy
854 \f