Package dependency cycles

While working on support for Racket packages in Guix, I learned that packages can have cyclic dependencies. Cycles seem rare, but, since one cycle involves base and racket-lib, they have to be accounted for from the beginning. So, I'd like to check my tentative understanding of how package dependency cycles work in practice.

First, according to the script at the bottom of this post, these are all of the cycles in the main package catalog:

;; Ignoring build-deps:
  ("collections-lib" "functional-lib")
  ("drracket" "quickscript")
  ("deinprogramm-signature" "htdp-lib")
  ("stxparse-info" "subtemplate"))
;; Considering build-deps:
  ("collections-lib" "functional-lib")
  ("drracket" "drracket-tool-doc" "quickscript")
  ("collections-doc" "functional-doc")
  ("graphite-doc" "graphite-tutorial")
  ("deinprogramm-signature" "htdp-lib")
  ("lens-common" "lens-data")
  ("peg-gen" "typed-peg")
  ("net-test" "racket-test")
  ("stxparse-info" "subtemplate")
  ("graphics" "w3s"))

(I'm not sure if this list reflects Reduce racket-doc dependencies. by samth · Pull Request #3215 · racket/racket · GitHub .)

Some questions:

  1. For packages involved in a cycle through deps (as opposed to build-deps only), it seems like they always need to be built at the same time, and they will also always need to be installed together. Is that correct?
  2. Likewise, do I understand correctly that packages involved in a cycle through build-deps need to be built at the same time?
  3. Even if installing "built packages" in the sense of 5 Source, Binary, and Built Packages, do packages involved in cycles through build-deps still all have to be installed together? It seems like they do—that only converting to "binary" or "binary library" packages would allow build-deps to be dropped—but that had not been my first guess.

Here is the script I used to look for cycles:

#lang racket

(require pkg/lib

(define-runtime-path archive-state.sqlite
(define-runtime-path archive/
;; this is a little convoluted to preserve deps vs build-deps
(unless (file-exists? (build-path archive/ "LOCK"))
  (parameterize ([current-pkg-lookup-version ""])
    (pkg-catalog-archive archive/
                         #:package-exn-handler void
                         #:state-catalog archive-state.sqlite)))
(parameterize ([current-directory (build-path archive/ "pkgs")])
  (for ([pth (in-directory)]
        #:when (equal? #".zip" (path-get-extension pth)))
    (define dir
      (path-replace-extension pth #""))
    (unless (directory-exists? dir)
      (unzip pth
             (make-filesystem-entry-reader #:dest dir)))
    (define compiled-dir
      (build-path dir "compiled"))
    (when (directory-exists? compiled-dir)
      (delete-directory/files compiled-dir))))

(define-values (pkgs invert-pkgs)
  (get-pkgs #:srcs (list (cons 'dir (build-path archive/ "pkgs")))
            #:roots '()
            #:quiet #false
            #:no-build? #false))

(define-values (reps no-build-reps depths max-depth at-depth)
  (get-cliques pkgs))

(define (group-cycles reps)
  (for/fold ([cycles #hash()])
            ([{pkg rep} (in-hash reps)])
    (hash-update cycles
                 (λ (members)
                   (hash-set members pkg #t))
                 (λ ()
                   (hash rep #t)))))

(define (show-cycles label reps)
  (displayln label)
   (hash-map (group-cycles reps)
             (λ (rep members)
               (hash-keys members 'ordered))

(show-cycles ";; Ignoring build-deps:" no-build-reps)
(displayln (make-string 80 #\;))
(show-cycles ";; Considering build-deps:" reps)

"Yes" to all.

I was a little surprised to see all the native-library packages in a cycle with "base". It makes some sense, but I'm not sure I noticed when I created the cycle. Maybe it would work and be better to reduce the native-library package dependencies to "racket". Or maybe it doesn't matter.