Detecting Dependencies in Common Lisp Project Files

Question

The following short program is a collection of routines for detecting the dependencies among a project’s component files. Dependencies serve as a rough measure of the complexity of a program. Minimizing inter-file dependencies is a worthy goal, since understanding and refactoring a complex program is often challenging. However, Common Lisp can support a wide latitude of inter-file dependencies within a compilation unit, so it is generally not advisable to sacrifice program modularity in order to remove all dependencies.

This analysis of inter-file dependencies is applied to the files in a specified directory. The pathname for this directory is assumed to be the value of *default-pathname-defaults*, which must be assigned before detecting dependencies. Which files are included is determined by supplying a standard Common Lisp filespec, which defaults to “*.lisp”.

A simple example of a dependency is the situation where a function is defined in one file, but used in a different file. In this case the using file depends on the defining file. But there are a number of other kinds of definitional dependencies checked besides defun, including defmacro, defparameter, defvar, defmethod, and defstruct.

More complex examples of dependencies include codependencies, where several files depend on each other. If two files each contain definitions used by the other, then they are codependent. Multiple files can be circularly dependent on each other, also making them codependent.

The amount of information printed to the terminal can be controlled by the key parameter verbose. The verbose option indicates why the files are dependent. For example, entering (display-all-dependencies) at the REPL simply prints out all detected file dependencies. But entering (display-all-dependencies :verbose t) will additionally show which symbols in the dependent file have definitions in another file.

Interface

function: display-all-dependencies (&key (pathspec "*.lisp") verbose)

Prints out all the dependencies and codependencies among all the files matching the directory pathspec in *default-pathname-defaults*

function: file-depends-on-what (file1 &key (pathspec "*.lisp") verbose)

Prints out all the files which a given file depends on.

function: file1-depends-on-file2 (file1 file2 &key verbose)

Determines if file1 depends on file2.

;;; Filename:  dependencies.lisp

;;; Finds the dependencies among files (ie, inter-file references) in a project directory.
;;; Assumes the project files have already been loaded, and
;;; that *default-pathname-defaults* points to the project directory.


(in-package :cl-user)


#-:alexandria (progn (ql:quickload :alexandria) (push :alexandria *features*))
#-:cl-ppcre (ql:quickload :cl-ppcre)


(use-package :alexandria)
(use-package :cl-ppcre)


(defun purify-file (file)
  "Transform problematic symbols to benign nil in file, before reading.
   Returns a string of altered file content."
  (let ((file-string (alexandria:read-file-into-string file)))
    (ppcre:regex-replace-all
      "[ \t\r\n]'[A-Za-z0-9!@$%&*_+:=<.>/?-]+"
      file-string " nil")
    (ppcre:regex-replace-all
      "[(][qQ][uU][oO][tT][eE][ \t\r\n]+[A-Za-z0-9!@$%&*_+:=<.>/?-]+[)]"
      file-string "nil")))
    

(defun collect-symbols (tree)
  "Collects all of the symbols in a form."
  (let ((all-items (alexandria:flatten tree)))
    (delete-if (lambda (item)
                 (or (not (symbolp item))
                     (find-symbol (symbol-name item) :cl)))
               (delete-duplicates all-items))))


(defun collect-defs (forms)
  "Collects all of the defined names in forms, excluding defstructs."
  (loop for form in forms
        when (member (first form)
               '(defun defmacro defparameter defvar defmethod))
        collect (second form)))


(defun collect-defstructs (forms)
  "Collects all of the defined defstruct names in forms."
  (loop for form in forms
        when (member (first form) 
               '(defstruct))
         if (symbolp (second form))
           collect (second form)
           else if (listp (second form))
                  collect (first (second form))))


(defun pseudo-load (file)
  "Attempt to read a file doing what LOAD would do. May not always do the right thing.
   Returns list of all forms, including package prefixes. Based on function provided
   by tfb on Stack Overflow."
  (let ((file-string (purify-file file))
        (*package* *package*))
    (with-input-from-string (in-stream file-string)
      (loop for form = (read in-stream nil in-stream)
            while (not (eql form in-stream))
            when (and (consp form)
                      (eq (first form) 'in-package))
             do (setf *package* (find-package (second form)))
            collect form))))


(defun file1-depends-on-file2 (file1 file2 &key verbose)
  "Determines if file1 depends on file2."
  (let* ((1forms (pseudo-load file1))
         (all1-syms (collect-symbols 1forms))
         (defstruct1-syms (collect-defstructs 1forms))
         (1syms (set-difference all1-syms defstruct1-syms :test #'equal))
         (forms2 (pseudo-load file2))
         (def2-syms (collect-defs forms2))
         (defstruct2-syms (collect-defstructs forms2))
         (11syms (loop for defstruct2-sym in defstruct2-syms
                   append (loop for 1sym in 1syms
                            when (and (not (eql defstruct2-sym 1sym))
                                      (search (format nil "~S" defstruct2-sym)
                                              (format nil "~S" 1sym)))
                             collect 1sym))))
    (when verbose
      (format t "~%~A symbols:~%~S~%" file1 1syms)
      (format t "~%~A symbols:~%~S~%" file2 def2-syms)
      (format t "~%~A structures:~%~S~%" file2 defstruct2-syms)
      (format t "~%~A symbols dependent on ~A:~%" file1 file2))
    (append (intersection 1syms def2-syms)
            11syms)))


(defun file-depends-on-what (file1 &key (pathspec "*.lisp") verbose)
  "Prints out all dependencies of a file in directory = *default-pathname-defaults*."
  (let ((files (mapcar #'file-namestring (directory pathspec))))
    (loop for file2 in files
          unless (equal file1 file2)
           do (let ((deps (file1-depends-on-file2 file1 file2)))
                (when deps
                  (if verbose
                    (format t "~%~A depends on ~A~%~S~%"
                            (file-namestring file1) (file-namestring file2) deps)
                    (format t "~%~A depends on ~A~%"
                            (file-namestring file1) (file-namestring file2))))))))


(defun all-path-cycles (node current-path adjacency-table)
  "Recursively follow all paths in a dependency network."
  (if (member node current-path :test #'equal)
    (list (subseq current-path 0 (1+ (position node current-path :test #'equal))))
    (loop for child in (gethash node adjacency-table)
          append (all-path-cycles child (cons node current-path) adjacency-table))))


(defun codependents (node-list dependencies)
  "Returns all dependent cycles for all nodes."
  (let ((adjacency-table (make-hash-table :test #'equal)))
    (loop for dep in dependencies
          do (push (second dep) (gethash (first dep) adjacency-table)))
    (loop for node in node-list
          append (all-path-cycles node nil adjacency-table))))


(defun display-codependencies (dependencies)
  "Prints out all codependencies among a group of files."
  (format t "~%Codependent files (with circular reference):~%")
  (let* ((node-list (remove-duplicates (alexandria:flatten dependencies)
                                       :test #'equal))
         (codependents (remove-duplicates (codependents node-list dependencies)
                                          :test (lambda (set1 set2)
                                                  (alexandria:set-equal set1 set2
                                                                        :test #'equal)))))
    (loop for co-set in codependents
          do (format t "~S~%" co-set))))
    
  
(defun display-all-dependencies (&key (pathspec "*.lisp") verbose)
  "Prints out all dependencies of every pathspec file in 
   directory = *default-pathname-defaults*."
  (let ((files (mapcar #'file-namestring (directory pathspec))))
    (loop with dependencies
          for file1 in files
          do (loop for file2 in files
                   unless (equal file1 file2)
                     do (let ((deps (file1-depends-on-file2 file1 file2)))
                          (when deps
                            (push (list file1 file2) dependencies)
                            (if verbose
                              (format t "~%~A depends on ~A~%~S~%"
                                      (file-namestring file1) (file-namestring file2) deps)
                              (format t "~%~A depends on ~A~%"
                                      (file-namestring file1) (file-namestring file2))))))
          finally (display-codependencies dependencies))))

Answer 1

Some general comments first. And to prefix that, at a glance the code itself looks quite alright to me, I just have some comments on the details to make it even nicer.

Arguably the first thing to note is to create an ASDF definition and don't require QuickLisp as the main loading mechanism. That usually entails one more .asd file and is otherwise painless. It will also allow you and others to easily load the whole system with one function from other systems.

#-:alexandria - that's usually written as #-alexandria as the *features* list mostly contains keywords anyway and, more importantly, the reader function for #- reads the argument as a keyword unless otherwise specified.

The use-package calls should go into the to-be-written defpackage declaration.

The functions all have docstrings, which is good, though it might also help to specify a bit more what the types of the inputs and outputs are. You could of course also add check-type / declare statements to make those explicit, but for me, the reader, something like "Returns a LIST of all dependent cycles for all nodes." would already be enough to satisfy my curiosity.

IMO, T and NIL should be written uppercase. That's because they're way too special to not have them stand out more.

Pathspecs should probably be written #P"*.lisp" to be very clear about the type.

I'm a bit wary of the flatten calls, but if you think that the additional allocations aren't a problem, then it's probably fine. It's just a point for optimisation to avoid too many intermediate lists.

If the equal tests could be replaced with eql or eq, it might also be better, but I'm not sure that's possible.

For file1-depends-on-file2, the name is actually mostly fine by me, though usuallya boolean-ish result would warrant file1-depends-on-file2-p ("predicate"). Also the verbose can probably be a regular argument if this isn't going to be called by a user directly. In it though, the names keyed by their source file look very awkward. Consider a helper function via flet/labels or even defun to get rid of the duplication and weird naming.

It also stands out to me that intersection isn't using :test, but the other call to set-difference does - is that a bug? It might even make sense to define some helpers with the right equality relation baked in eventually.

The format calls look good, only in display-all-dependencies I'd consider merging the verbose and non-verbose case via ~@[~A~] and the argument (and verbose deps) (so combined that'd be (format T "...~@[~A~]~%" ... (and verbose deps))).

loop is a bit over-used IMO when you have two loops inside each other. It also looks like this would be better abstracted by a helper function that creates a list of all those pairs of files, there might even be one in the alexandria or arnesi packages.

Pairs like (list file1 file2) might very well just use a single cons cell too, so (cons file1 file2) would suffice (and makes it absolutely clear it's a pair).

Lastly, for loading the files, the purify-file function attempts to throw away "problematic" symbols, which are what, quoted symbols? I don't exactly see why this function, like it is, helps a lot. Instead what I'd probably suggest, is to disable evaluation of code when read is called (e.g. you don't want to execute anything while reading the files, something like (read-from-string "#.(format T \"Hello, world!~%\")")) quite handily demonstrates the dangers). Setting *read-suppress* to true would be a start, or even setting *read-eval* to false. See also with-standard-io-syntax.