\chapter{Cross-Referencing Facility}
\label{xref}
\cindex{cross-referencing}
\credits{by Eric Marsden}

The \cmucl{} cross-referencing facility (abbreviated XREF) assists in
the analysis of static dependency relationships in a program. It
provides introspection capabilities such as the ability to know which
functions may call a given function, and the program contexts in which
a particular global variable is used. The compiler populates a
database of cross-reference information, which can be queried by the
user to know:

\begin{itemize}
\item
the list of program contexts (functions, macros, top-level forms)
where a given function may be called at runtime, either directly or
indirectly (via its function-object);

\item
the list of program contexts where a given global variable may be
read;

\item
the list of program contexts that bind a global variable;

\item
the list of program contexts where a given global variable may be
modified during the execution of the program.
\end{itemize}

A global variable is either a dynamic variable or a constant variable,
for instance declared using \code{defvar} or \code{defparameter} or
\code{defconstant}.


\section{Populating the cross-reference database}

\begin{defvar}{c:}{record-xref-info}
   When non-NIL, code that is compiled (either using
   \code{compile-file}, or by calling \code{compile} from the
   listener), will be analyzed for cross-references. Defaults to
   \nil{}.
\end{defvar}

Cross-referencing information is only generated by the compiler; the
interpreter does not populate the cross-reference database. XREF
analysis is independent of whether the compiler is generating native
code or byte code, and of whether it is compiling from a file, from a
stream, or is invoked interactively from the listener. 

Alternatively, the \kwd{:xref} option to \code{compile-file} may be
specified to populate the cross-reference database when compiling a
file.  In this case, loading the generated fasl file in a fresh lisp
will also populate the cross-reference database.

\begin{defun}{xref:}{init-xref-database}{}
  Reinitializes the database of cross-references. This can be used to
  reclaim the space occupied by the database contents, or to discard
  stale cross-reference information.
\end{defun}



\section{Querying the cross-reference database}

\cmucl{} provides a number of functions in the XREF package that may
be used to query the cross-reference database:

\begin{defun}{xref:}{who-calls}{\args \var{function}}
   Returns the list of xref-contexts where \var{function} (either a
   symbol that names a function, or a function object) may be called
   at runtime. XREF does not record calls to macro-functions (such as
   \code{defun}) or to special forms (such as \code{eval-when}).
\end{defun}

\begin{defun}{xref:}{who-references}{\args \var{global-variable}}
   Returns the list of program contexts that may reference
   \var{global-variable}. 
\end{defun}

\begin{defun}{xref:}{who-binds}{\args \var{global-variable}}
  Returns a list of program contexts where the specified global
  variable may be bound at runtime (for example using \code{LET}).
\end{defun}

\begin{defun}{xref:}{who-sets}{\args \var{global-variable}}
  Returns a list of program contexts where the given global variable
  may be modified at runtime (for example using \code{SETQ}). 
\end{defun}

An \textit{xref-context} is the originating site of a cross-reference.
It identifies a portion of a program, and is defined by an
\code{xref-context} structure, that comprises a name, a source file and a
source-path. 

\begin{defun}{xref:}{xref-context-name}{\args \var{context}}
  Returns the name slot of an xref-context, which is one of:
\begin{itemize}
\item
a global function, which is named by a symbol or by a list of the form
\code{(setf\ foo)}. 

\item
a macro, named by a list \verb|(:macro foo)|.

\item
an inner function (\code{flet}, \code{labels}, or anonymous lambdas) that
is named by a list of the form \code{(:internal outer inner)}.

\item
a method, named by a list of the form
\verb|(:method foo (specializer1 specializer2)|. 

\item
a string \verb|"Top-Level Form"| that identifies a reference from a
top-level form. Note that multiple references from top-level forms
will only be listed once. 

\item
a compiler-macro, named by a string of the form
\verb|(:compiler-macro foo)|. 

\item
a string such as \verb|"DEFSTRUCT FOO"|, identifying a reference from
within a structure accessor or constructor or copier.

\item
a string such as 
\begin{verbatim}
  "Creation Form for #<KERNEL::CLASS-CELL STRUCT-FOO>"
\end{verbatim}

\item
a string such as \verb|"defun foo"|, or \verb|"defmethod bar (t)"|,
that identifies a reference from within code that has been generated
by the compiler for that form. For example, the compilation of a
\code{defclass} form causes accessor functions to be generated by the
compiler; this code is compiler-generated (it does not appear in the
source file), and so is identified by the XREF facility by a string. 
\end{itemize}
\end{defun}


\begin{defun}{xref:}{xref-context-file}{\var{context}}
  Return the truename (in the sense of the variable
   \vindexed{compile-file-truename}) of the source file from which the
   referencing forms were compiled. This slot will be \nil{} if the
   code was compiled from a stream, or interactively from the
   listener.
\end{defun}

\begin{defun}{xref:}{xref-context-source-path}{\var{context}}
  Return a list of positive integers identifying the form that
  contains the cross-reference. The first integer in the source-path
  is the number of the top-level form containing the cross-reference
  (for example, 2 identifies the second top-level form in the source
  file). The second integer in the source-path identifies the form
  within this top-level form that contains the cross-reference, and so
  on. This function will always return \nil{} if the file slot of an
  xref-context is \nil{}.

% While walking the top-level form, count one in depth-first order for
% each subform that is a cons.
\end{defun}




\section{Example usage}

In this section, we will illustrate use of the XREF facility on a
number of simple examples.

Consider the following program fragment, that defines a global
variable and a function.

\begin{verbatim}
  (defvar *variable-one* 42)
  
  (defun function-one (x)
     (princ (* x *variable-one*)))
\end{verbatim}

We save this code in a file named \code{example.lisp}, enable
cross-referencing, clear any previous cross-reference information,
compile the file, and can then query the cross-reference database
(output has been modified for readability).

\begin{verbatim}
  USER> (setf c:*record-xref-info* t)
  USER> (xref:init-xref-database)
  USER> (compile-file "example")
  USER> (xref:who-calls 'princ)
  (#<xref-context function-one in #p"example.lisp">)
  USER> (xref:who-references '*variable-one*)
  (#<xref-context function-one in #p"example.lisp">)
\end{verbatim}

From this example, we see that the compiler has noted the call to the
global function \code{princ} in \code{function-one}, and the reference
to the global variable \code{*variable-one*}. 

Suppose that we add the following code to the previous file. 

\begin{verbatim}
(defconstant +constant-one+ 1)
  
(defstruct struct-one
  slot-one
  (slot-two +constant-one+ :type integer)
  (slot-three 42 :read-only t))

(defmacro with-different-one (&body body)
  `(let ((*variable-one* 666))
      ,@body))

(defun get-variable-one () *variable-one*)

(defun (setf get-variable-one) (new-value)
  (setq *variable-one* new-value))
\end{verbatim}

In the following example, we detect references x and y.


% FIXME add function with LABELS, a binding, a set



The following function illustrates the effect that various forms of
optimization carried out by the \cmucl{} compiler can have on the
cross-references that are reported for a particular program. The
compiler is able to detect that the evaluated condition is always
false, and that the first clause of the \code{if} will never be taken
(this optimization is called dead-code elimination). XREF will
therefore not register a call to the function \code{sin} from the
function \code{foo}. Likewise, no calls to the functions \code{sqrt}
and \code{\textless} are registered, because the compiler has eliminated the
code that evaluates the condition. Finally, no call to the function
\code{expt} is generated, because the compiler was able to evaluate
the result of the expression \code{(expt 3 2)} at compile-time (though
a process called constant-folding).

\begin{verbatim}
;; zero call references are registered for this function!
(defun constantly-nine (x)
  (if (< (sqrt x) 0)
      (sin x)
      (expt 3 2)))
\end{verbatim}


\section{Limitations of the cross-referencing facility}

No cross-reference information is available for interpreted functions.
The cross-referencing database is not persistent: unless you save an
image using \code{save-lisp}, the database will be empty each time
\cmucl{} is restarted. There is no mechanism that saves
cross-reference information in FASL files, so loading a system from
compiled code will not populate the cross-reference database. The XREF
database currently accumulates ``stale'' information: when compiling a
file, it does not delete any cross-references that may have previously
been generated for that file. This latter limitation will be removed
in a future release. 

The cross-referencing facility is only able to analyze the static
dependencies in a program; it does not provide any information about
runtime (dynamic) dependencies. For instance, XREF is able to identify
the list of program contexts where a given function may be called, but
is not able to determine which contexts will be activated when the
program is executed with a specific set of input parameters. However,
the static analysis that is performed by the \cmucl{} compiler does
allow XREF to provide more information than would be available from a
mere syntactic analysis of a program. References that occur from
within unreachable code will not be displayed by XREF, because the
\cmucl{} compiler deletes dead code before cross-references are
analyzed. Certain ``trivial'' function calls (where the result of the
function call can be evaluated at compile-time) may be eliminated by
optimizations carried out by the compiler; see the example below.

If you examine the entire database of cross-reference information (by
accessing undocumented internals of the XREF package), you will note
that XREF notes ``bogus'' cross-references to function calls that are
inserted by the compiler. For example, in safe code, the \cmucl{}
compiler inserts a call to an internal function called
\code{c::\%verify-argument-count}, so that the number of arguments
passed to the function is checked each time it is called. The XREF
facility does not distinguish between user code and these forms that
are introduced during compilation. This limitation should not be
visible if you use the documented functions in the XREF package. 

As of the 18e release of \cmucl{}, the cross-referencing facility is
experimental; expect details of its implementation to change in future
releases. In particular, the names given to CLOS methods and to inner
functions will change in future releases.