aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLudovic Courtès <ludo@gnu.org>2019-12-10 20:13:04 +0100
committerLudovic Courtès <ludo@gnu.org>2019-12-11 12:12:58 +0100
commitddd59159004ca73c9449a27945116ff5069c3743 (patch)
tree9212db3dbfdc22d62afdc92643e5dbdd91f06399
parent6c3021a84006924d924d282f22aa1f338d4b3528 (diff)
downloadguix-ddd59159004ca73c9449a27945116ff5069c3743.tar
guix-ddd59159004ca73c9449a27945116ff5069c3743.tar.gz
import: utils: 'recursive-import' returns packages in topological order.
* guix/import/utils.scm (topological-sort): New procedure. (recursive-import): Rewrite to use it. * tests/import-utils.scm ("recursive-import"): New test. * guix/import/cran.scm (cran->guix-package): Always return two values. * guix/scripts/import/cran.scm (guix-import-cran): Remove 'reverse' call on 'cran-recursive-import' result. * guix/scripts/import/crate.scm (guix-import-crate): Likewise. * guix/scripts/import/elpa.scm (guix-import-elpa): Likewise. * guix/scripts/import/gem.scm (guix-import-gem): Likewise. * guix/scripts/import/hackage.scm (guix-import-hackage): Likewise. * guix/scripts/import/opam.scm (guix-import-opam): Likewise. * guix/scripts/import/pypi.scm (guix-import-pypi): Likewise. * guix/scripts/import/stackage.scm (guix-import-stackage): Likewise. * tests/gem.scm ("gem-recursive-import"): Change the order of package expressions accordingly.
-rw-r--r--guix/import/cran.scm4
-rw-r--r--guix/import/utils.scm84
-rw-r--r--guix/scripts/import/cran.scm7
-rw-r--r--guix/scripts/import/crate.scm5
-rw-r--r--guix/scripts/import/elpa.scm7
-rw-r--r--guix/scripts/import/gem.scm5
-rw-r--r--guix/scripts/import/hackage.scm5
-rw-r--r--guix/scripts/import/opam.scm5
-rw-r--r--guix/scripts/import/pypi.scm5
-rw-r--r--guix/scripts/import/stackage.scm5
-rw-r--r--tests/gem.scm22
-rw-r--r--tests/import-utils.scm25
12 files changed, 105 insertions, 74 deletions
diff --git a/guix/import/cran.scm b/guix/import/cran.scm
index e47aff2b12..d9018cc7da 100644
--- a/guix/import/cran.scm
+++ b/guix/import/cran.scm
@@ -1,6 +1,6 @@
;;; GNU Guix --- Functional package management for GNU
;;; Copyright © 2015, 2016, 2017, 2018, 2019 Ricardo Wurmus <rekado@elephly.net>
-;;; Copyright © 2015, 2016, 2017 Ludovic Courtès <ludo@gnu.org>
+;;; Copyright © 2015, 2016, 2017, 2019 Ludovic Courtès <ludo@gnu.org>
;;; Copyright © 2017 Mathieu Othacehe <m.othacehe@gmail.com>
;;;
;;; This file is part of GNU Guix.
@@ -505,7 +505,7 @@ s-expression corresponding to that package, or #f on failure."
((bioconductor)
;; Retry import from CRAN
(cran->guix-package package-name 'cran))
- (else #f)))))))
+ (else (values #f '()))))))))
(define* (cran-recursive-import package-name #:optional (repo 'cran))
(recursive-import package-name repo
diff --git a/guix/import/utils.scm b/guix/import/utils.scm
index 4694b6e7ef..ef7c13259d 100644
--- a/guix/import/utils.scm
+++ b/guix/import/utils.scm
@@ -34,12 +34,14 @@
#:use-module (guix gexp)
#:use-module (guix store)
#:use-module (guix download)
+ #:use-module (guix sets)
#:use-module (gnu packages)
#:use-module (ice-9 match)
#:use-module (ice-9 rdelim)
#:use-module (ice-9 receive)
#:use-module (ice-9 regex)
#:use-module (srfi srfi-1)
+ #:use-module (srfi srfi-9)
#:use-module (srfi srfi-11)
#:use-module (srfi srfi-26)
#:use-module (srfi srfi-41)
@@ -377,40 +379,54 @@ separated by PRED."
(chr (char-downcase chr)))
name)))
+(define (topological-sort nodes
+ node-dependencies
+ node-name)
+ "Perform a breadth-first traversal of the graph rooted at NODES, a list of
+nodes, and return the list of nodes sorted in topological order. Call
+NODE-DEPENDENCIES to obtain the dependencies of a node, and NODE-NAME to
+obtain a node's uniquely identifying \"key\"."
+ (let loop ((nodes nodes)
+ (result '())
+ (visited (set)))
+ (match nodes
+ (()
+ result)
+ ((head . tail)
+ (if (set-contains? visited (node-name head))
+ (loop tail result visited)
+ (let ((dependencies (node-dependencies head)))
+ (loop (append dependencies tail)
+ (cons head result)
+ (set-insert (node-name head) visited))))))))
+
(define* (recursive-import package-name repo
#:key repo->guix-package guix-name
#:allow-other-keys)
- "Generate a stream of package expressions for PACKAGE-NAME and all its
-dependencies."
- (define (exists? dependency)
- (not (null? (find-packages-by-name (guix-name dependency)))))
- (define initial-state (list #f (list package-name) (list)))
- (define (step state)
- (match state
- ((prev (next . rest) done)
- (define (handle? dep)
- (and
- (not (equal? dep next))
- (not (member dep done))
- (not (exists? dep))))
- (receive (package . dependencies) (repo->guix-package next repo)
- (list
- (if package package '()) ;; default #f on failure would interrupt
- (if package
- (lset-union equal? rest (filter handle? (car dependencies)))
- rest)
- (cons next done))))
- ((prev '() done)
- (list #f '() done))))
-
- ;; Generate a lazy stream of package expressions for all unknown
- ;; dependencies in the graph.
- (stream-unfold
- ;; map: produce a stream element
- (match-lambda ((latest queue done) latest))
- ;; predicate
- (match-lambda ((latest queue done) latest))
- ;; generator: update the queue
- step
- ;; initial state
- (step initial-state)))
+ "Return a stream of package expressions for PACKAGE-NAME and all its
+dependencies, sorted in topological order. For each package,
+call (REPO->GUIX-PACKAGE NAME REPO), which should return a package expression
+and a list of dependencies; call (GUIX-NAME NAME) to obtain the Guix package
+name corresponding to the upstream name."
+ (define-record-type <node>
+ (make-node name package dependencies)
+ node?
+ (name node-name)
+ (package node-package)
+ (dependencies node-dependencies))
+
+ (define (exists? name)
+ (not (null? (find-packages-by-name (guix-name name)))))
+
+ (define (lookup-node name)
+ (receive (package dependencies) (repo->guix-package name repo)
+ (make-node name package dependencies)))
+
+ (list->stream ;TODO: remove streams
+ (map node-package
+ (topological-sort (list (lookup-node package-name))
+ (lambda (node)
+ (map lookup-node
+ (remove exists?
+ (node-dependencies node))))
+ node-name))))
diff --git a/guix/scripts/import/cran.scm b/guix/scripts/import/cran.scm
index b6592f78a9..d47be584ae 100644
--- a/guix/scripts/import/cran.scm
+++ b/guix/scripts/import/cran.scm
@@ -98,10 +98,9 @@ Import and convert the CRAN package for PACKAGE-NAME.\n"))
(if (assoc-ref opts 'recursive)
;; Recursive import
(map package->definition
- (reverse
- (stream->list
- (cran-recursive-import package-name
- (or (assoc-ref opts 'repo) 'cran)))))
+ (stream->list
+ (cran-recursive-import package-name
+ (or (assoc-ref opts 'repo) 'cran))))
;; Single import
(let ((sexp (cran->guix-package package-name
(or (assoc-ref opts 'repo) 'cran))))
diff --git a/guix/scripts/import/crate.scm b/guix/scripts/import/crate.scm
index 4690cceb4d..a388dc368d 100644
--- a/guix/scripts/import/crate.scm
+++ b/guix/scripts/import/crate.scm
@@ -101,9 +101,8 @@ Import and convert the crate.io package for PACKAGE-NAME.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (crate-recursive-import name))))
+ (stream->list
+ (crate-recursive-import name)))
(let ((sexp (crate->guix-package name version)))
(unless sexp
(leave (G_ "failed to download meta-data for package '~a'~%")
diff --git a/guix/scripts/import/elpa.scm b/guix/scripts/import/elpa.scm
index f1ed5016ba..3cdb49eae4 100644
--- a/guix/scripts/import/elpa.scm
+++ b/guix/scripts/import/elpa.scm
@@ -101,10 +101,9 @@ Import the latest package named PACKAGE-NAME from an ELPA repository.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (elpa-recursive-import package-name
- (or (assoc-ref opts 'repo) 'gnu)))))
+ (stream->list
+ (elpa-recursive-import package-name
+ (or (assoc-ref opts 'repo) 'gnu))))
(let ((sexp (elpa->guix-package package-name (assoc-ref opts 'repo))))
(unless sexp
(leave (G_ "failed to download package '~a'~%") package-name))
diff --git a/guix/scripts/import/gem.scm b/guix/scripts/import/gem.scm
index b6d9ccaae4..afd7bf6d3e 100644
--- a/guix/scripts/import/gem.scm
+++ b/guix/scripts/import/gem.scm
@@ -95,9 +95,8 @@ Import and convert the RubyGems package for PACKAGE-NAME.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (gem-recursive-import package-name 'rubygems))))
+ (stream->list
+ (gem-recursive-import package-name 'rubygems)))
(let ((sexp (gem->guix-package package-name)))
(unless sexp
(leave (G_ "failed to download meta-data for package '~a'~%")
diff --git a/guix/scripts/import/hackage.scm b/guix/scripts/import/hackage.scm
index f4aac61078..023cc1e700 100644
--- a/guix/scripts/import/hackage.scm
+++ b/guix/scripts/import/hackage.scm
@@ -130,9 +130,8 @@ version.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (apply hackage-recursive-import arguments))))
+ (stream->list
+ (apply hackage-recursive-import arguments)))
;; Single import
(apply hackage->guix-package arguments))))
(unless sexp (error-fn))
diff --git a/guix/scripts/import/opam.scm b/guix/scripts/import/opam.scm
index 2d249a213f..10410f714d 100644
--- a/guix/scripts/import/opam.scm
+++ b/guix/scripts/import/opam.scm
@@ -94,9 +94,8 @@ Import and convert the opam package for PACKAGE-NAME.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (opam-recursive-import package-name))))
+ (stream->list
+ (opam-recursive-import package-name)))
;; Single import
(let ((sexp (opam->guix-package package-name)))
(unless sexp
diff --git a/guix/scripts/import/pypi.scm b/guix/scripts/import/pypi.scm
index 7bd83818ba..f5f34b3c1b 100644
--- a/guix/scripts/import/pypi.scm
+++ b/guix/scripts/import/pypi.scm
@@ -95,9 +95,8 @@ Import and convert the PyPI package for PACKAGE-NAME.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (pypi-recursive-import package-name))))
+ (stream->list
+ (pypi-recursive-import package-name)))
;; Single import
(let ((sexp (pypi->guix-package package-name)))
(unless sexp
diff --git a/guix/scripts/import/stackage.scm b/guix/scripts/import/stackage.scm
index b4b12581bf..9325341c84 100644
--- a/guix/scripts/import/stackage.scm
+++ b/guix/scripts/import/stackage.scm
@@ -110,9 +110,8 @@ Import and convert the LTS Stackage package for PACKAGE-NAME.\n"))
`(define-public ,(string->symbol name)
,pkg))
(_ #f))
- (reverse
- (stream->list
- (apply stackage-recursive-import arguments))))
+ (stream->list
+ (apply stackage-recursive-import arguments)))
;; Single import
(apply stackage->guix-package arguments))))
(unless sexp (error-fn))
diff --git a/tests/gem.scm b/tests/gem.scm
index a12edb294c..82b2c3cea1 100644
--- a/tests/gem.scm
+++ b/tests/gem.scm
@@ -123,22 +123,21 @@
(_ (error "Unexpected URL: " url)))))
(match (stream->list (gem-recursive-import "foo"))
((('package
- ('name "ruby-foo")
+ ('name "ruby-bar")
('version "1.0.0")
('source
('origin
('method 'url-fetch)
- ('uri ('rubygems-uri "foo" 'version))
+ ('uri ('rubygems-uri "bar" 'version))
('sha256
('base32
"1a270mlajhrmpqbhxcqjqypnvgrq4pgixpv3w9gwp1wrrapnwrzk"))))
('build-system 'ruby-build-system)
('propagated-inputs
('quasiquote
- (("bundler" ('unquote 'bundler))
- ("ruby-bar" ('unquote 'ruby-bar)))))
- ('synopsis "A cool gem")
- ('description "This package provides a cool gem")
+ (('"bundler" ('unquote 'bundler)))))
+ ('synopsis "Another cool gem")
+ ('description "Another cool gem")
('home-page "https://example.com")
('license ('list 'license:expat 'license:asl2.0)))
('package
@@ -157,21 +156,22 @@
('home-page "https://bundler.io/")
('license 'license:expat))
('package
- ('name "ruby-bar")
+ ('name "ruby-foo")
('version "1.0.0")
('source
('origin
('method 'url-fetch)
- ('uri ('rubygems-uri "bar" 'version))
+ ('uri ('rubygems-uri "foo" 'version))
('sha256
('base32
"1a270mlajhrmpqbhxcqjqypnvgrq4pgixpv3w9gwp1wrrapnwrzk"))))
('build-system 'ruby-build-system)
('propagated-inputs
('quasiquote
- (('"bundler" ('unquote 'bundler)))))
- ('synopsis "Another cool gem")
- ('description "Another cool gem")
+ (("bundler" ('unquote 'bundler))
+ ("ruby-bar" ('unquote 'ruby-bar)))))
+ ('synopsis "A cool gem")
+ ('description "This package provides a cool gem")
('home-page "https://example.com")
('license ('list 'license:expat 'license:asl2.0))))
#t)
diff --git a/tests/import-utils.scm b/tests/import-utils.scm
index c3ab25d788..3400433bbb 100644
--- a/tests/import-utils.scm
+++ b/tests/import-utils.scm
@@ -24,7 +24,9 @@
#:use-module (guix packages)
#:use-module (guix build-system)
#:use-module (gnu packages)
- #:use-module (srfi srfi-64))
+ #:use-module (srfi srfi-41)
+ #:use-module (srfi srfi-64)
+ #:use-module (ice-9 match))
(test-begin "import-utils")
@@ -41,6 +43,27 @@
'license:lgpl2.0
(license->symbol license:lgpl2.0))
+(test-equal "recursive-import"
+ '((package ;package expressions in topological order
+ (name "bar"))
+ (package
+ (name "foo")
+ (inputs `(("bar" ,bar)))))
+ (stream->list
+ (recursive-import "foo" 'repo
+ #:repo->guix-package
+ (match-lambda*
+ (("foo" 'repo)
+ (values '(package
+ (name "foo")
+ (inputs `(("bar" ,bar))))
+ '("bar")))
+ (("bar" 'repo)
+ (values '(package
+ (name "bar"))
+ '())))
+ #:guix-name identity)))
+
(test-assert "alist->package with simple source"
(let* ((meta '(("name" . "hello")
("version" . "2.10")