;;;; This file contains the optimization machinery for make-instance.

;;;; This software is part of the SBCL system. See the README file for
;;;; more information.

;;;; This software is derived from software originally released by
;;;; Gerd Moellmann.  Copyright and release statements follow.  Later
;;;; modifications to the software are in the public domain and are
;;;; provided with absolutely no warranty.  See the COPYING and
;;;; CREDITS files for more information.

;;; Copyright (C) 2002 Gerd Moellmann <gerd.moellmann@t-online.de>
;;; All rights reserved.
;;;
;;; Redistribution and use in source and binary forms, with or without
;;; modification, are permitted provided that the following conditions
;;; are met:
;;;
;;; 1. Redistributions of source code must retain the above copyright
;;;    notice, this list of conditions and the following disclaimer.
;;; 2. Redistributions in binary form must reproduce the above copyright
;;;    notice, this list of conditions and the following disclaimer in the
;;;    documentation and/or other materials provided with the distribution.
;;; 3. The name of the author may not be used to endorse or promote
;;;    products derived from this software without specific prior written
;;;    permission.
;;;
;;; THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
;;; OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
;;; WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
;;; ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
;;; LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
;;; CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
;;; OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
;;; BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
;;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
;;; USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
;;; DAMAGE.

;;; ***************
;;; Overview  *****
;;; ***************
;;;
;;; Compiler macro for MAKE-INSTANCE, and load-time generation of
;;; optimized instance constructor functions.
;;;
;;; ********************
;;; Entry Points  ******
;;; ********************
;;;
;;; UPDATE-CTORS must be called when methods are added/removed,
;;; classes are changed, etc., which affect instance creation.
;;;
;;; PRECOMPILE-CTORS can be called to precompile constructor functions
;;; for classes whose definitions are known at the time the function
;;; is called.

(in-package "SB-PCL")

;;; ******************
;;; Utilities  *******
;;; ******************

(defun quote-plist-keys (plist)
  (loop for (key . more) on plist by #'cddr
        if (null more) do
          (error "Not a property list: ~S" plist)
        else
          collect `(quote ,key)
          and collect (car more)))

(defun plist-keys (plist &key test)
  (loop for (key . more) on plist by #'cddr
        if (null more) do
          (error "Not a property list: ~S" plist)
        else if (or (null test) (funcall test key))
          collect key))

(defun plist-values (plist &key test)
  (loop for (key . more) on plist by #'cddr
        if (null more) do
          (error "Not a property list: ~S" plist)
        else if (or (null test) (funcall test (car more)))
          collect (car more)))

(defun constant-class-arg-p (form)
  (and (constantp form)
       (let ((constant (constant-form-value form)))
         (or (and (symbolp constant)
                  (not (null (symbol-package constant))))
             (classp form)))))

(defun constant-symbol-p (form)
  (and (constantp form)
       (let ((constant (constant-form-value form)))
         (and (symbolp constant)
              (not (null (symbol-package constant)))))))

;;; Somewhat akin to DEFAULT-INITARGS, but just collecting the defaulted
;;; initargs for the call.
(defun ctor-default-initkeys (supplied-initargs class-default-initargs)
  (loop for (key) in class-default-initargs
        when (eq (getf supplied-initargs key '.not-there.) '.not-there.)
        collect key))

;;; Like DEFAULT-INITARGS, but return a list that can be spliced into source,
;;; instead of a list with values already evaluated.
(defun ctor-default-initargs (supplied-initargs class-default-initargs)
  (loop for (key form fun) in class-default-initargs
        when (eq (getf supplied-initargs key '.not-there.) '.not-there.)
        append (list key (if (constantp form) form `(funcall ,fun)))
          into default-initargs
        finally
          (return (append supplied-initargs default-initargs))))

;;; *****************
;;; CTORS   *********
;;; *****************
;;;
;;; Ctors are funcallable instances whose initial function is a
;;; function computing an optimized constructor function when called.
;;; When the optimized function is computed, the function of the
;;; funcallable instance is set to it.
;;;
(!defstruct-with-alternate-metaclass ctor
  :slot-names (function-name class-or-name class initargs safe-p)
  :boa-constructor %make-ctor
  :superclass-name function
  :metaclass-name static-classoid
  :metaclass-constructor make-static-classoid
  :dd-type funcallable-structure
  :runtime-type-checks-p nil)

;;; List of all defined ctors.
(defvar *all-ctors* ())

(defun make-ctor-parameter-list (ctor)
  (plist-values (ctor-initargs ctor) :test (complement #'constantp)))

;;; Reset CTOR to use a default function that will compute an
;;; optimized constructor function when called.
(defun install-initial-constructor (ctor &key force-p)
  (when (or force-p (ctor-class ctor))
    (setf (ctor-class ctor) nil)
    (setf (funcallable-instance-fun ctor)
          #'(lambda (&rest args)
              (install-optimized-constructor ctor)
              (apply ctor args)))
    (setf (%funcallable-instance-info ctor 1)
          (ctor-function-name ctor))))

(defun make-ctor-function-name (class-name initargs safe-code-p)
  (list* 'ctor class-name safe-code-p initargs))

;;; Keep this a separate function for testing.
(defun ensure-ctor (function-name class-name initargs safe-code-p)
  (with-world-lock ()
    (if (fboundp function-name)
        (the ctor (fdefinition function-name))
        (make-ctor function-name class-name initargs safe-code-p))))

;;; Keep this a separate function for testing.
(defun make-ctor (function-name class-name initargs safe-p)
  (without-package-locks ; for (setf symbol-function)
    (let ((ctor (%make-ctor function-name class-name nil initargs safe-p)))
      (install-initial-constructor ctor :force-p t)
      (push ctor *all-ctors*)
      (setf (fdefinition function-name) ctor)
      ctor)))

;;; *****************
;;; Inline CTOR cache
;;; *****************
;;;
;;; The cache starts out as a list of CTORs, sorted with the most recently
;;; used CTORs near the head. If it expands too much, we switch to a vector
;;; with a simple hashing scheme.

;;; Find CTOR for KEY (which is a class or class name) in a list. If the CTOR
;;; is in the list but not one of the 4 first ones, return a new list with the
;;; found CTOR at the head. Thread-safe: the new list shares structure with
;;; the old, but is not desctructively modified. Returning the old list for
;;; hits close to the head reduces ping-ponging with multiple threads seeking
;;; the same list.
(defun find-ctor (key list)
  (labels ((walk (tail from-head depth)
             (declare (fixnum depth))
             (if tail
                 (let ((ctor (car tail)))
                   (if (eq (ctor-class-or-name ctor) key)
                       (if (> depth 3)
                           (values ctor
                                   (nconc (list ctor) (nreverse from-head) (cdr tail)))
                           (values ctor
                                   list))
                       (walk (cdr tail)
                             (cons ctor from-head)
                             (logand #xf (1+ depth)))))
                 (values nil list))))
    (walk list nil 0)))

(declaim (inline sxhash-symbol-or-class))
(defun sxhash-symbol-or-class (x)
  (cond ((symbolp x) (sxhash x))
        ((std-instance-p x) (std-instance-hash x))
        ((fsc-instance-p x) (fsc-instance-hash x))
        (t
         (bug "Something strange where symbol or class expected."))))

;;; Max number of CTORs kept in an inline list cache. Once this is
;;; exceeded we switch to a table.
(defconstant +ctor-list-max-size+ 12)
;;; Max table size for CTOR cache. If the table fills up at this size
;;; we keep the same size and drop 50% of the old entries.
(defconstant +ctor-table-max-size+ (expt 2 8))
;;; Even if there is space in the cache, if we cannot fit a new entry
;;; with max this number of collisions we expand the table (if possible)
;;; and rehash.
(defconstant +ctor-table-max-probe-depth+ 5)

(defun make-ctor-table (size)
  (declare (index size))
  (let ((real-size (power-of-two-ceiling size)))
    (if (< real-size +ctor-table-max-size+)
        (values (make-array real-size :initial-element nil) nil)
        (values (make-array +ctor-table-max-size+ :initial-element nil) t))))

(declaim (inline mix-ctor-hash))
(defun mix-ctor-hash (hash base)
  (logand most-positive-fixnum (+ hash base 1)))

(defun put-ctor (ctor table)
  (cond ((try-put-ctor ctor table)
         (values ctor table))
        (t
         (expand-ctor-table ctor table))))

;;; Thread-safe: if two threads write to the same index in parallel, the other
;;; result is just lost. This is not an issue as the CTORs are used as their
;;; own keys. If both were EQ, we're good. If non-EQ, the next time the other
;;; one is needed we just cache it again -- hopefully not getting stomped on
;;; that time.
(defun try-put-ctor (ctor table)
  (declare (simple-vector table) (optimize speed))
  (let* ((class (ctor-class-or-name ctor))
         (base (sxhash-symbol-or-class class))
         (hash base)
         (mask (1- (length table))))
    (declare (fixnum base hash mask))
    (loop repeat +ctor-table-max-probe-depth+
          do (let* ((index (logand mask hash))
                    (old (aref table index)))
               (cond ((and old (neq class (ctor-class-or-name old)))
                      (setf hash (mix-ctor-hash hash base)))
                     (t
                      (setf (aref table index) ctor)
                      (return-from try-put-ctor t)))))
    ;; Didn't fit, must expand
    nil))

(defun get-ctor (class table)
  (declare (simple-vector table) (optimize speed))
  (let* ((base (sxhash-symbol-or-class class))
         (hash base)
         (mask (1- (length table))))
    (declare (fixnum base hash mask))
    (loop repeat +ctor-table-max-probe-depth+
          do (let* ((index (logand mask hash))
                    (old (aref table index)))
               (if (and old (eq class (ctor-class-or-name old)))
                   (return-from get-ctor old)
                   (setf hash (mix-ctor-hash hash base)))))
    ;; Nothing.
    nil))

;;; Thread safe: the old table is read, but if another thread mutates
;;; it while we're reading we still get a sane result -- either the old
;;; or the new entry. The new table is locally allocated, so that's ok
;;; too.
(defun expand-ctor-table (ctor old)
  (declare (simple-vector old))
  (let* ((old-size (length old))
         (new-size (* 2 old-size))
         (drop-random-entries nil))
    (tagbody
     :again
       (multiple-value-bind (new max-size-p) (make-ctor-table new-size)
         (let ((action (if drop-random-entries
                           ;; Same logic as in method caches -- see comment
                           ;; there.
                           (randomly-punting-lambda (old-ctor)
                             (try-put-ctor old-ctor new))
                           (lambda (old-ctor)
                             (unless (try-put-ctor old-ctor new)
                               (if max-size-p
                                   (setf drop-random-entries t)
                                   (setf new-size (* 2 new-size)))
                               (go :again))))))
           (aver (try-put-ctor ctor new))
           (dotimes (i old-size)
             (let ((old-ctor (aref old i)))
               (when old-ctor
                 (funcall action old-ctor))))
           (return-from expand-ctor-table (values ctor new)))))))

(defun ctor-list-to-table (list)
  (let ((table (make-ctor-table (length list))))
    (dolist (ctor list)
      (setf table (nth-value 1 (put-ctor ctor table))))
    table))

(defun ensure-cached-ctor (class-name store initargs safe-code-p)
  (flet ((maybe-ctor-for-caching ()
           (if (typep class-name '(or symbol class))
               (let ((name (make-ctor-function-name class-name initargs safe-code-p)))
                 (ensure-ctor name class-name initargs safe-code-p))
               ;; Invalid first argument: let MAKE-INSTANCE worry about it.
               (return-from ensure-cached-ctor
                 (values (lambda (&rest ctor-parameters)
                           (let (mi-initargs)
                             (doplist (key value) initargs
                               (push key mi-initargs)
                               (push (if (constantp value)
                                         value
                                         (pop ctor-parameters))
                                     mi-initargs))
                             (apply #'make-instance class-name (nreverse mi-initargs))))
                         store)))))
    (if (listp store)
        (multiple-value-bind (ctor list) (find-ctor class-name store)
          (if ctor
              (values ctor list)
              (let ((ctor (maybe-ctor-for-caching)))
                (if (< (length list) +ctor-list-max-size+)
                    (values ctor (cons ctor list))
                    (values ctor (ctor-list-to-table list))))))
       (let ((ctor (get-ctor class-name store)))
         (if ctor
             (values ctor store)
             (put-ctor (maybe-ctor-for-caching) store))))))

;;; ***********************************************
;;; Compile-Time Expansion of MAKE-INSTANCE *******
;;; ***********************************************

(defvar *compiling-optimized-constructor* nil)

(define-compiler-macro make-instance (&whole form &rest args &environment env)
  (declare (ignore args))
  ;; Compiling an optimized constructor for a non-standard class means compiling a
  ;; lambda with (MAKE-INSTANCE #<SOME-CLASS X> ...) in it -- need
  ;; to make sure we don't recurse there.
  (or (unless *compiling-optimized-constructor*
        (make-instance->constructor-call form (safe-code-p env)))
      form))

(defun make-instance->constructor-call (form safe-code-p)
  (destructuring-bind (class-arg &rest args) (cdr form)
    (flet (;;
           ;; Return the name of parameter number I of a constructor
           ;; function.
           (parameter-name (i)
             (let ((ps #(.p0. .p1. .p2. .p3. .p4. .p5.)))
               (if (array-in-bounds-p ps i)
                   (aref ps i)
                   (format-symbol *pcl-package* ".P~D." i))))
           ;; Check if CLASS-ARG is a constant symbol.  Give up if
           ;; not.
           (constant-class-p ()
             (and class-arg (constant-class-arg-p class-arg)))
           ;; Check if ARGS are suitable for an optimized constructor.
           ;; Return NIL from the outer function if not.
           (check-args ()
             (loop for (key . more) on args by #'cddr do
                      (when (or (null more)
                                (not (constant-symbol-p key))
                                (eq :allow-other-keys (constant-form-value key)))
                        (return-from make-instance->constructor-call nil)))))
      (check-args)
      ;; Collect a plist of initargs and constant values/parameter names
      ;; in INITARGS.  Collect non-constant initialization forms in
      ;; VALUE-FORMS.
      (multiple-value-bind (initargs value-forms)
          (loop for (key value) on args by #'cddr and i from 0
                collect (constant-form-value key) into initargs
                if (constantp value)
                collect value into initargs
                else
                collect (parameter-name i) into initargs
                and collect value into value-forms
                finally
                (return (values initargs value-forms)))
        (if (constant-class-p)
            (let* ((class-or-name (constant-form-value class-arg))
                   (function-name (make-ctor-function-name class-or-name initargs
                                                           safe-code-p)))
              ;; Prevent compiler warnings for calling the ctor.
              (proclaim-as-fun-name function-name)
              (note-name-defined function-name :function)
              (when (eq (info :function :where-from function-name) :assumed)
                (setf (info :function :where-from function-name) :defined)
                (when (info :function :assumed-type function-name)
                  (setf (info :function :assumed-type function-name) nil)))
              ;; Return code constructing a ctor at load time, which, when
              ;; called, will set its funcallable instance function to an
              ;; optimized constructor function.
              `(locally
                   (declare (disable-package-locks ,function-name))
                 (let ((.x. (load-time-value
                             (ensure-ctor ',function-name ',class-or-name ',initargs
                                          ',safe-code-p))))
                   (declare (ignore .x.))
                   ;; ??? check if this is worth it.
                   (declare
                    (ftype (or (function ,(make-list (length value-forms)
                                                     :initial-element t)
                                         t)
                               (function (&rest t) t))
                           ,function-name))
                   (funcall (function ,function-name) ,@value-forms))))
            (when (and class-arg (not (constantp class-arg)))
              ;; Build an inline cache: a CONS, with the actual cache in the CDR.
              `(locally (declare (disable-package-locks .cache. .class-arg. .store. .fun.
                                                        make-instance))
                 (let* ((.cache. (load-time-value (cons 'ctor-cache nil)))
                        (.store. (cdr .cache.))
                        (.class-arg. ,class-arg))
                   (multiple-value-bind (.fun. .new-store.)
                       (ensure-cached-ctor .class-arg. .store. ',initargs ',safe-code-p)
                     ;; Thread safe: if multiple threads hit this in paralle, the update
                     ;; from the other one is just lost -- no harm done, except for the
                     ;; need to redo the work next time.
                     (unless (eq .store. .new-store.)
                       (setf (cdr .cache.) .new-store.))
                     (funcall (truly-the function .fun.) ,@value-forms))))))))))

;;; **************************************************
;;; Load-Time Constructor Function Generation  *******
;;; **************************************************

;;; The system-supplied primary INITIALIZE-INSTANCE and
;;; SHARED-INITIALIZE methods.  One cannot initialize these variables
;;; to the right values here because said functions don't exist yet
;;; when this file is first loaded.
(defvar *the-system-ii-method* nil)
(defvar *the-system-si-method* nil)

(defun install-optimized-constructor (ctor)
  (with-world-lock ()
    (let* ((class-or-name (ctor-class-or-name ctor))
           (class (if (symbolp class-or-name)
                      (find-class class-or-name)
                      class-or-name)))
      (unless (class-finalized-p class)
        (finalize-inheritance class))
      ;; We can have a class with an invalid layout here.  Such a class
      ;; cannot have a LAYOUT-INVALID of (:FLUSH ...) or (:OBSOLETE
      ;; ...), because part of the deal is that those only happen from
      ;; FORCE-CACHE-FLUSHES, which create a new valid wrapper for the
      ;; class.  An invalid layout of T needs to be flushed, however.
      (when (eq (layout-invalid (class-wrapper class)) t)
        (%force-cache-flushes class))
      (setf (ctor-class ctor) class)
      (pushnew ctor (plist-value class 'ctors) :test #'eq)
      (setf (funcallable-instance-fun ctor)
            (multiple-value-bind (form locations names)
                (constructor-function-form ctor)
              (apply
               (let ((*compiling-optimized-constructor* t))
                 (handler-bind ((compiler-note #'muffle-warning))
                   (compile nil `(lambda ,names ,form))))
               locations))))))

(defun constructor-function-form (ctor)
  (let* ((class (ctor-class ctor))
         (proto (class-prototype class))
         (make-instance-methods
          (compute-applicable-methods #'make-instance (list class)))
         (allocate-instance-methods
          (compute-applicable-methods #'allocate-instance (list class)))
         ;; I stared at this in confusion for a while, thinking
         ;; carefully about the possibility of the class prototype not
         ;; being of sufficient discrimiating power, given the
         ;; possibility of EQL-specialized methods on
         ;; INITIALIZE-INSTANCE or SHARED-INITIALIZE.  However, given
         ;; that this is a constructor optimization, the user doesn't
         ;; yet have the instance to create a method with such an EQL
         ;; specializer.
         ;;
         ;; There remains the (theoretical) possibility of someone
         ;; coming along with code of the form
         ;;
         ;; (defmethod initialize-instance :before ((o foo) ...)
         ;;   (eval `(defmethod shared-initialize :before ((o foo) ...) ...)))
         ;;
         ;; but probably we can afford not to worry about this too
         ;; much for now.  -- CSR, 2004-07-12
         (ii-methods
          (compute-applicable-methods #'initialize-instance (list proto)))
         (si-methods
          (compute-applicable-methods #'shared-initialize (list proto t)))
         (setf-svuc-slots-methods
          (loop for slot in (class-slots class)
                collect (compute-applicable-methods
                         #'(setf slot-value-using-class)
                         (list nil class proto slot))))
         (sbuc-slots-methods
          (loop for slot in (class-slots class)
                collect (compute-applicable-methods
                         #'slot-boundp-using-class
                         (list class proto slot)))))
    ;; Cannot initialize these variables earlier because the generic
    ;; functions don't exist when PCL is built.
    (when (null *the-system-si-method*)
      (setq *the-system-si-method*
            (find-method #'shared-initialize
                         () (list *the-class-slot-object* *the-class-t*)))
      (setq *the-system-ii-method*
            (find-method #'initialize-instance
                         () (list *the-class-slot-object*))))
    ;; Note that when there are user-defined applicable methods on
    ;; MAKE-INSTANCE and/or ALLOCATE-INSTANCE, these will show up
    ;; together with the system-defined ones in what
    ;; COMPUTE-APPLICABLE-METHODS returns.
    (let ((maybe-invalid-initargs
           (check-initargs-1
            class
            (append
             (ctor-default-initkeys
              (ctor-initargs ctor) (class-default-initargs class))
             (plist-keys (ctor-initargs ctor)))
            (append ii-methods si-methods) nil nil))
          (custom-make-instance
           (not (null (cdr make-instance-methods)))))
      (if (and (not (structure-class-p class))
               (not (condition-class-p class))
               (not custom-make-instance)
               (null (cdr allocate-instance-methods))
               (every (lambda (x)
                        (member (slot-definition-allocation x)
                                '(:instance :class)))
                      (class-slots class))
               (not maybe-invalid-initargs)
               (not (around-or-nonstandard-primary-method-p
                     ii-methods *the-system-ii-method*))
               (not (around-or-nonstandard-primary-method-p
                     si-methods *the-system-si-method*))
               ;; the instance structure protocol goes through
               ;; slot-value(-using-class) and friends (actually just
               ;; (SETF SLOT-VALUE-USING-CLASS) and
               ;; SLOT-BOUNDP-USING-CLASS), so if there are non-standard
               ;; applicable methods we can't shortcircuit them.
               (every (lambda (x) (= (length x) 1)) setf-svuc-slots-methods)
               (every (lambda (x) (= (length x) 1)) sbuc-slots-methods))
          (optimizing-generator ctor ii-methods si-methods)
          (fallback-generator ctor ii-methods si-methods
                              (or maybe-invalid-initargs custom-make-instance))))))

(defun around-or-nonstandard-primary-method-p
    (methods &optional standard-method)
  (loop with primary-checked-p = nil
        for method in methods
        as qualifiers = (if (consp method)
                            (early-method-qualifiers method)
                            (safe-method-qualifiers method))
        when (or (eq :around (car qualifiers))
                 (and (null qualifiers)
                      (not primary-checked-p)
                      (not (null standard-method))
                      (not (eq standard-method method))))
          return t
        when (null qualifiers) do
          (setq primary-checked-p t)))

(defun fallback-generator (ctor ii-methods si-methods use-make-instance)
  (declare (ignore ii-methods si-methods))
  (let ((class (ctor-class ctor))
        (lambda-list (make-ctor-parameter-list ctor))
        (initargs (quote-plist-keys (ctor-initargs ctor))))
    (if use-make-instance
        `(lambda ,lambda-list
           (declare #.*optimize-speed*)
           ;; The CTOR MAKE-INSTANCE optimization checks for
           ;; *COMPILING-OPTIMIZED-CONSTRUCTOR* which is bound around compilation of
           ;; the constructor, hence avoiding the possibility of endless recursion.
           (make-instance ,class ,@initargs))
        (let ((defaults (class-default-initargs class)))
          (when defaults
            (setf initargs (ctor-default-initargs initargs defaults)))
          `(lambda ,lambda-list
             (declare #.*optimize-speed*)
             (fast-make-instance ,class ,@initargs))))))

;;; Not as good as the real optimizing generator, but faster than going
;;; via MAKE-INSTANCE: 1 GF call less, and no need to check initargs.
(defun fast-make-instance (class &rest initargs)
  (declare #.*optimize-speed*)
  (declare (dynamic-extent initargs))
  (let ((.instance. (apply #'allocate-instance class initargs)))
    (apply #'initialize-instance .instance. initargs)
    .instance.))

(defun optimizing-generator (ctor ii-methods si-methods)
  (multiple-value-bind (locations names body before-method-p)
      (fake-initialization-emf ctor ii-methods si-methods)
    (let ((wrapper (class-wrapper (ctor-class ctor))))
      (values
       `(lambda ,(make-ctor-parameter-list ctor)
         (declare #.*optimize-speed*)
         (block nil
           (when (layout-invalid ,wrapper)
             (install-initial-constructor ,ctor)
             (return (funcall ,ctor ,@(make-ctor-parameter-list ctor))))
           ,(wrap-in-allocate-forms ctor body before-method-p)))
       locations
       names))))

;;; Return a form wrapped around BODY that allocates an instance
;;; constructed by CTOR.  BEFORE-METHOD-P set means we have to run
;;; before-methods, in which case we initialize instance slots to
;;; +SLOT-UNBOUND+.  The resulting form binds the local variables
;;; .INSTANCE. to the instance, and .SLOTS. to the instance's slot
;;; vector around BODY.
(defun wrap-in-allocate-forms (ctor body before-method-p)
  (let* ((class (ctor-class ctor))
         (wrapper (class-wrapper class))
         (allocation-function (raw-instance-allocator class))
         (slots-fetcher (slots-fetcher class)))
    (if (eq allocation-function 'allocate-standard-instance)
        `(let ((.instance. (%make-standard-instance nil
                                                    (get-instance-hash-code)))
               (.slots. (make-array
                         ,(layout-length wrapper)
                         ,@(when before-method-p
                             '(:initial-element +slot-unbound+)))))
           (setf (std-instance-wrapper .instance.) ,wrapper)
           (setf (std-instance-slots .instance.) .slots.)
           ,body
           .instance.)
        `(let* ((.instance. (,allocation-function ,wrapper))
                (.slots. (,slots-fetcher .instance.)))
           (declare (ignorable .slots.))
           ,body
           .instance.))))

;;; Return a form for invoking METHOD with arguments from ARGS.  As
;;; can be seen in METHOD-FUNCTION-FROM-FAST-FUNCTION, method
;;; functions look like (LAMBDA (ARGS NEXT-METHODS) ...).  We could
;;; call fast method functions directly here, but benchmarks show that
;;; there's no speed to gain, so lets avoid the hair here.
(defmacro invoke-method (method args)
  `(funcall ,(method-function method) ,args ()))

;;; Return a form that is sort of an effective method comprising all
;;; calls to INITIALIZE-INSTANCE and SHARED-INITIALIZE that would
;;; normally have taken place when calling MAKE-INSTANCE.
(defun fake-initialization-emf (ctor ii-methods si-methods)
  (multiple-value-bind (ii-around ii-before ii-primary ii-after)
      (standard-sort-methods ii-methods)
    (declare (ignore ii-primary))
    (multiple-value-bind (si-around si-before si-primary si-after)
        (standard-sort-methods si-methods)
      (declare (ignore si-primary))
      (aver (and (null ii-around) (null si-around)))
      (let ((initargs (ctor-initargs ctor)))
        (multiple-value-bind (locations names bindings vars defaulting-initargs body)
            (slot-init-forms ctor (or ii-before si-before))
        (values
         locations
         names
         `(let ,bindings
           (declare (ignorable ,@vars))
           (let (,@(when (or ii-before ii-after)
                     `((.ii-args.
                        (list .instance. ,@(quote-plist-keys initargs) ,@defaulting-initargs))))
                 ,@(when (or si-before si-after)
                     `((.si-args.
                        (list .instance. t ,@(quote-plist-keys initargs) ,@defaulting-initargs)))))
            ,@(loop for method in ii-before
                    collect `(invoke-method ,method .ii-args.))
            ,@(loop for method in si-before
                    collect `(invoke-method ,method .si-args.))
            ,@body
            ,@(loop for method in si-after
                    collect `(invoke-method ,method .si-args.))
            ,@(loop for method in ii-after
                    collect `(invoke-method ,method .ii-args.))))
         (or ii-before si-before)))))))

;;; Return four values from APPLICABLE-METHODS: around methods, before
;;; methods, the applicable primary method, and applicable after
;;; methods.  Before and after methods are sorted in the order they
;;; must be called.
(defun standard-sort-methods (applicable-methods)
  (loop for method in applicable-methods
        as qualifiers = (if (consp method)
                            (early-method-qualifiers method)
                            (safe-method-qualifiers method))
        if (null qualifiers)
          collect method into primary
        else if (eq :around (car qualifiers))
          collect method into around
        else if (eq :after (car qualifiers))
          collect method into after
        else if (eq :before (car qualifiers))
          collect method into before
        finally
          (return (values around before (first primary) (reverse after)))))

(defmacro with-type-checked ((type safe-p) &body body)
  (if safe-p
      ;; To handle FUNCTION types reasonable, we use SAFETY 3 and
      ;; THE instead of e.g. CHECK-TYPE.
      `(locally
           (declare (optimize (safety 3)))
         (the ,type (progn ,@body)))
      `(progn ,@body)))

;;; Return as multiple values bindings for default initialization
;;; arguments, variable names, defaulting initargs and a body for
;;; initializing instance and class slots of an object costructed by
;;; CTOR.  The variable .SLOTS. is assumed to bound to the instance's
;;; slot vector.  BEFORE-METHOD-P T means before-methods will be
;;; called, which means that 1) other code will initialize instance
;;; slots to +SLOT-UNBOUND+ before the before-methods are run, and
;;; that we have to check if these before-methods have set slots.
(defun slot-init-forms (ctor before-method-p)
  (let* ((class (ctor-class ctor))
         (initargs (ctor-initargs ctor))
         (initkeys (plist-keys initargs))
         (safe-p (ctor-safe-p ctor))
         (slot-vector
          (make-array (layout-length (class-wrapper class))
                      :initial-element nil))
         (class-inits ())
         (default-inits ())
         (defaulting-initargs ())
         (default-initargs (class-default-initargs class))
         (initarg-locations
          (compute-initarg-locations
           class (append initkeys (mapcar #'car default-initargs)))))
    (labels ((initarg-locations (initarg)
               (cdr (assoc initarg initarg-locations :test #'eq)))
             (initializedp (location)
               (cond
                 ((consp location)
                  (assoc location class-inits :test #'eq))
                 ((integerp location)
                  (not (null (aref slot-vector location))))
                 (t (bug "Weird location in ~S" 'slot-init-forms))))
             (class-init (location kind val type)
               (aver (consp location))
               (unless (initializedp location)
                 (push (list location kind val type) class-inits)))
             (instance-init (location kind val type)
               (aver (integerp location))
               (unless (initializedp location)
                 (setf (aref slot-vector location) (list kind val type))))
             (default-init-var-name (i)
               (let ((ps #(.d0. .d1. .d2. .d3. .d4. .d5.)))
                 (if (array-in-bounds-p ps i)
                     (aref ps i)
                     (format-symbol *pcl-package* ".D~D." i))))
             (location-var-name (i)
               (let ((ls #(.l0. .l1. .l2. .l3. .l4. .l5.)))
                 (if (array-in-bounds-p ls i)
                     (aref ls i)
                     (format-symbol *pcl-package* ".L~D." i)))))
      ;; Loop over supplied initargs and values and record which
      ;; instance and class slots they initialize.
      (loop for (key value) on initargs by #'cddr
            as kind = (if (constantp value) 'constant 'param)
            as locations = (initarg-locations key)
            do (loop for (location . type) in locations
                     do (if (consp location)
                            (class-init location kind value type)
                            (instance-init location kind value type))))
      ;; Loop over default initargs of the class, recording
      ;; initializations of slots that have not been initialized
      ;; above.  Default initargs which are not in the supplied
      ;; initargs are treated as if they were appended to supplied
      ;; initargs, that is, their values must be evaluated even
      ;; if not actually used for initializing a slot.
      (loop for (key initform initfn) in default-initargs and i from 0
            unless (member key initkeys :test #'eq)
            do (let* ((kind (if (constantp initform) 'constant 'var))
                      (init (if (eq kind 'var) initfn initform)))
                 (ecase kind
                   (constant
                    (push (list 'quote key) defaulting-initargs)
                    (push initform defaulting-initargs))
                   (var
                    (push (list 'quote key) defaulting-initargs)
                    (push (default-init-var-name i) defaulting-initargs)))
              (when (eq kind 'var)
                (let ((init-var (default-init-var-name i)))
                  (setq init init-var)
                  (push (cons init-var initfn) default-inits)))
              (loop for (location . type) in (initarg-locations key)
                    do (if (consp location)
                           (class-init location kind init type)
                           (instance-init location kind init type)))))
      ;; Loop over all slots of the class, filling in the rest from
      ;; slot initforms.
      (loop for slotd in (class-slots class)
            as location = (slot-definition-location slotd)
            as type = (slot-definition-type slotd)
            as allocation = (slot-definition-allocation slotd)
            as initfn = (slot-definition-initfunction slotd)
            as initform = (slot-definition-initform slotd) do
              (unless (or (eq allocation :class)
                          (null initfn)
                          (initializedp location))
                (if (constantp initform)
                    (instance-init location 'initform initform type)
                    (instance-init location 'initform/initfn initfn type))))
      ;; Generate the forms for initializing instance and class slots.
      (let ((instance-init-forms
             (loop for slot-entry across slot-vector and i from 0
                   as (kind value type) = slot-entry collect
                     (ecase kind
                       ((nil)
                        (unless before-method-p
                          `(setf (clos-slots-ref .slots. ,i) +slot-unbound+)))
                       ((param var)
                        `(setf (clos-slots-ref .slots. ,i)
                               (with-type-checked (,type ,safe-p)
                                   ,value)))
                       (initfn
                        `(setf (clos-slots-ref .slots. ,i)
                               (with-type-checked (,type ,safe-p)
                                 (funcall ,value))))
                       (initform/initfn
                        (if before-method-p
                            `(when (eq (clos-slots-ref .slots. ,i)
                                       +slot-unbound+)
                               (setf (clos-slots-ref .slots. ,i)
                                     (with-type-checked (,type ,safe-p)
                                       (funcall ,value))))
                            `(setf (clos-slots-ref .slots. ,i)
                                   (with-type-checked (,type ,safe-p)
                                     (funcall ,value)))))
                       (initform
                        (if before-method-p
                            `(when (eq (clos-slots-ref .slots. ,i)
                                       +slot-unbound+)
                               (setf (clos-slots-ref .slots. ,i)
                                     (with-type-checked (,type ,safe-p)
                                       ',(constant-form-value value))))
                            `(setf (clos-slots-ref .slots. ,i)
                                   (with-type-checked (,type ,safe-p)
                                     ',(constant-form-value value)))))
                       (constant
                        `(setf (clos-slots-ref .slots. ,i)
                               (with-type-checked (,type ,safe-p)
                                 ',(constant-form-value value))))))))
        ;; we are not allowed to modify QUOTEd locations, so we can't
        ;; generate code like (setf (cdr ',location) arg).  Instead,
        ;; we have to do (setf (cdr .L0.) arg) and arrange for .L0. to
        ;; be bound to the location.
        (multiple-value-bind (names locations class-init-forms)
            (loop for (location kind value type) in class-inits
                  for i upfrom 0
                  for name = (location-var-name i)
                  collect name into names
                  collect location into locations
                  collect `(setf (cdr ,name)
                                 (with-type-checked (,type ,safe-p)
                                   ,(case kind
                                          (constant `',(constant-form-value value))
                                          ((param var) `,value)
                                          (initfn `(funcall ,value)))))
                  into class-init-forms
                  finally (return (values names locations class-init-forms)))
          (multiple-value-bind (vars bindings)
              (loop for (var . initfn) in (nreverse default-inits)
                    collect var into vars
                    collect `(,var (funcall ,initfn)) into bindings
                    finally (return (values vars bindings)))
            (values locations names
                    bindings vars
                    (nreverse defaulting-initargs)
                    `(,@(delete nil instance-init-forms)
                      ,@class-init-forms))))))))

;;; Return an alist of lists (KEY (LOCATION . TYPE-SPECIFIER) ...)
;;; telling, for each key in INITKEYS, which locations the initarg
;;; initializes and the associated type with the location.  CLASS is
;;; the class of the instance being initialized.
(defun compute-initarg-locations (class initkeys)
  (loop with slots = (class-slots class)
        for key in initkeys collect
          (loop for slot in slots
                if (memq key (slot-definition-initargs slot))
                  collect (cons (slot-definition-location slot)
                                (slot-definition-type slot))
                          into locations
                else
                  collect slot into remaining-slots
                finally
                  (setq slots remaining-slots)
                  (return (cons key locations)))))


;;; *******************************
;;; External Entry Points  ********
;;; *******************************

(defun update-ctors (reason &key class name generic-function method)
  (labels ((reset (class &optional ri-cache-p (ctorsp t))
             (when ctorsp
               (dolist (ctor (plist-value class 'ctors))
                 (install-initial-constructor ctor)))
             (when ri-cache-p
               (setf (plist-value class 'ri-initargs) ()))
             (dolist (subclass (class-direct-subclasses class))
               (reset subclass ri-cache-p ctorsp))))
    (ecase reason
      ;; CLASS must have been specified.
      (finalize-inheritance
       (reset class t))
      ;; NAME must have been specified.
      (setf-find-class
       (loop for ctor in *all-ctors*
             when (eq (ctor-class-or-name ctor) name) do
             (when (ctor-class ctor)
               (reset (ctor-class ctor)))
             (loop-finish)))
      ;; GENERIC-FUNCTION and METHOD must have been specified.
      ((add-method remove-method)
       (flet ((class-of-1st-method-param (method)
                (type-class (first (method-specializers method)))))
         (case (generic-function-name generic-function)
           ((make-instance allocate-instance)
            ;; FIXME: I can't see a way of working out which classes a
            ;; given metaclass specializer are applicable to short of
            ;; iterating and testing with class-of.  It would be good
            ;; to not invalidate caches of system classes at this
            ;; point (where it is not legal to define a method
            ;; applicable to them on system functions).  -- CSR,
            ;; 2010-07-13
            (reset (find-class 'standard-object) t t))
           ((initialize-instance shared-initialize)
            (reset (class-of-1st-method-param method) t t))
           ((reinitialize-instance)
            (reset (class-of-1st-method-param method) t nil))
           (t (when (or (eq (generic-function-name generic-function)
                            'slot-boundp-using-class)
                        (equal (generic-function-name generic-function)
                               '(setf slot-value-using-class)))
                ;; this looks awfully expensive, but given that one
                ;; can specialize on the SLOTD argument, nothing is
                ;; safe.  -- CSR, 2004-07-12
                (reset (find-class 'standard-object))))))))))

(defun precompile-ctors ()
  (dolist (ctor *all-ctors*)
    (when (null (ctor-class ctor))
      (let ((class (find-class (ctor-class-or-name ctor) nil)))
        (when (and class (class-finalized-p class))
          (install-optimized-constructor ctor))))))

(defun check-ri-initargs (instance initargs)
  (let* ((class (class-of instance))
         (keys (plist-keys initargs))
         (cache (plist-value class 'ri-initargs))
         (cached (assoc keys cache :test #'equal))
         (invalid-keys
          (if (consp cached)
              (cdr cached)
              (let ((invalid
                     ;; FIXME: give CHECK-INITARGS-1 and friends a
                     ;; more mnemonic name and (possibly) a nicer,
                     ;; more orthogonal interface.
                     (check-initargs-1
                      class initargs
                      (list (list* 'reinitialize-instance instance initargs)
                            (list* 'shared-initialize instance nil initargs))
                      t nil)))
                (setf (plist-value class 'ri-initargs)
                      (acons keys invalid cache))
                invalid))))
    (when invalid-keys
      (error 'initarg-error :class class :initargs invalid-keys))))

;;; end of ctor.lisp