Chapter 12 Cross-Referencing Facility

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:

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);
the list of program contexts where a given global variable may be read;
the list of program contexts that bind a global variable;
the list of program contexts where a given global variable may be modified during the execution of the program.

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

12.1 Populating the cross-reference database

[Variable]
c:*record-xref-info*

When non-NIL, code that is compiled (either using compile-file, or by calling compile from the listener), will be analyzed for cross-references. Defaults to nil.

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.

[Function]
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.

12.2 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:

[Function]
xref:who-calls function

Returns the list of xref-contexts where 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 defun) or to special forms (such as eval-when).

[Function]
xref:who-references global-variable

Returns the list of program contexts that may reference global-variable.

[Function]
xref:who-binds global-variable

Returns a list of program contexts where the specified global variable may be bound at runtime (for example using LET).

[Function]
xref:who-sets global-variable

Returns a list of program contexts where the given global variable may be modified at runtime (for example using SETQ).

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

[Function]
xref:xref-context-name context

Returns the name slot of an xref-context, which is one of:
a global function, which is named by a symbol or by a list of the form (setf foo).

a macro, named by a list (:macro foo).

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

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

a string "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.

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

a string such as "DEFSTRUCT FOO", identifying a reference from within a structure accessor or constructor or copier.
a string such as
  "Creation Form for #<KERNEL::CLASS-CELL STRUCT-FOO>"
a string such as "defun foo", or "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 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.

[Function]
xref:xref-context-file context

Return the truename (in the sense of the variable *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.

[Function]
xref:xref-context-source-path 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.

12.3 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.

  (defvar *variable-one* 42)
  
  (defun function-one (x)
     (princ (* x *variable-one*)))

We save this code in a file named 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).

  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">)

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

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

(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))

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

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 if will never be taken (this optimization is called dead-code elimination). XREF will therefore not register a call to the function sin from the function foo. Likewise, no calls to the functions sqrt and < are registered, because the compiler has eliminated the code that evaluates the condition. Finally, no call to the function expt is generated, because the compiler was able to evaluate the result of the expression (expt 3 2) at compile-time (though a process called constant-folding).

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

12.4 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 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 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.