--- Begin Message ---
|
Subject: |
24.3; package.el dependency ordering incorrect (non-topological) |
|
Date: |
Wed, 12 Mar 2014 16:50:56 +1300 |
package.el does not resolve dependencies in the correct order,
potentially resulting in packages installed before their
dependencies. This was reported in #14082 [1], but not fixed for all
cases. The packages should be arranged in topological order before
installation.
Consider the following package graph, with dependencies flowing left to
right:
C
/ \ X---Z
A D--E \ /
\ / Y
B
Or as an `archive-contents'
(1
(a . [(1) ((b) (c)) "a" nil])
(b . [(1) ((d)) "b" nil])
(c . [(1) ((d)) "c" nil])
(d . [(1) ((e)) "d" nil])
(e . [(1) nil "e" nil])
(x . [(1) ((z) (y)) "x" nil])
(y . [(1) ((z)) "y" nil])
(z . [(1) nil "z" nil])
)
For a, the only valid install orders are (e d b c a) or (e d c b a)
For x, the only valid install order is (z y x)
When installing `a' or `x', the ordering may be incorrect:
emacs-version:
GNU Emacs 24.3.1 (x86_64-apple-darwin13.1.0, NS apple-appkit-1265.19)
of 2014-03-12 on argon.cons.org.nz
[FAIL] install a = (c e d b a)
[FAIL] install x = (y z x)
emacs-version:
GNU Emacs 24.3.50.1 (x86_64-apple-darwin13.1.0, NS apple-appkit-1265.19)
of 2014-03-12 on argon.cons.org.nz
[FAIL] install a = (d c e b a)
[ OK] install x = (z y x)
For convenience, the complete test can be found on github [2].
[1] http://debbugs.gnu.org/cgi/bugreport.cgi?bug=14082
[2] https://gist.github.com/thefloweringash/9500216
Regards,
Andrew
In GNU Emacs 24.3.1 (amd64-portbld-freebsd10.0, Motif Version 2.3.4)
of 2014-01-23 on 10R-amd64-default-job-01
Windowing system distributor `The X.Org Foundation', version 11.0.11404000
Configured using:
`configure '--localstatedir=/var' '--without-compress-info'
'--without-dbus' '--without-gconf' '--with-gif' '--with-gnutls'
'--without-gsettings' '--with-jpeg' '--with-m17n-flt'
'--with-imagemagick' '--with-libotf' '--with-png'
'--with-toolkit-scroll-bars' '--with-sound' '--with-rsvg'
'--with-sync-input' '--with-tiff' '--with-xft' '--with-xim'
'--with-xml2' '--with-xpm' '--with-x-toolkit=motif' '--with-x'
'--x-libraries=/usr/local/lib' '--x-includes=/usr/local/include'
'--prefix=/usr/local' '--mandir=/usr/local/man'
'--infodir=/usr/local/share/emacs/info/'
'--build=amd64-portbld-freebsd10.0'
'build_alias=amd64-portbld-freebsd10.0' 'CC=cc' 'CFLAGS=-O2 -pipe
-fno-strict-aliasing' 'LDFLAGS= -L/usr/local/lib
-Wl,-rpath=/usr/lib:/usr/local/lib' 'CPPFLAGS=-I/usr/local/include'
'CPP=cpp''
Important settings:
value of $LANG: en_NZ.UTF-8
locale-coding-system: utf-8-unix
default enable-multibyte-characters: t
Major mode: Fundamental
Minor modes in effect:
tooltip-mode: t
mouse-wheel-mode: t
tool-bar-mode: t
menu-bar-mode: t
file-name-shadow-mode: t
global-font-lock-mode: t
blink-cursor-mode: t
auto-composition-mode: t
auto-encryption-mode: t
auto-compression-mode: t
buffer-read-only: t
line-number-mode: t
transient-mark-mode: t
Recent input:
M-x r e p o r t - e m a c s - b u g <return>
Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.
Load-path shadows:
None found.
Features:
(shadow sort gnus-util mail-extr emacsbug message idna format-spec
rfc822 mml easymenu mml-sec mm-decode mm-bodies mm-encode mail-parse
rfc2231 mailabbrev gmm-utils mailheader sendmail rfc2047 rfc2045
ietf-drums mm-util mail-prsvr mail-utils time-date tooltip ediff-hook
vc-hooks lisp-float-type mwheel x-win x-dnd tool-bar dnd fontset image
regexp-opt fringe tabulated-list newcomment lisp-mode register page
menu-bar rfn-eshadow timer select scroll-bar mouse jit-lock font-lock
syntax facemenu font-core frame cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese hebrew greek
romanian slovak czech european ethiopic indian cyrillic chinese
case-table epa-hook jka-cmpr-hook help simple abbrev minibuffer loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote make-network-process dynamic-setting font-render-setting motif
x-toolkit x multi-tty emacs)
--- End Message ---
--- Begin Message ---
|
Subject: |
Re: bug#16994: 24.3; package.el dependency ordering incorrect (non-topological) |
|
Date: |
Tue, 06 May 2014 14:13:45 -0400 |
|
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) |
> package.el does not resolve dependencies in the correct order,
> potentially resulting in packages installed before their
> dependencies. This was reported in #14082 [1], but not fixed for all
> cases. The packages should be arranged in topological order before
> installation.
Indeed, thanks. I installed the patch below which should make the sort
truly topological. It also adds detection of dependency cycles since
this new topological sorting would otherwise get into an inf-loop
in that case.
Stefan
=== modified file 'lisp/emacs-lisp/package.el'
--- lisp/emacs-lisp/package.el 2014-03-28 22:47:46 +0000
+++ lisp/emacs-lisp/package.el 2014-05-06 18:07:45 +0000
@@ -868,7 +868,7 @@
;; Also check built-in packages.
(package-built-in-p package min-version)))
-(defun package-compute-transaction (packages requirements)
+(defun package-compute-transaction (packages requirements &optional seen)
"Return a list of packages to be installed, including PACKAGES.
PACKAGES should be a list of `package-desc'.
@@ -880,7 +880,9 @@
This function recursively computes the requirements of the
packages in REQUIREMENTS, and returns a list of all the packages
that must be installed. Packages that are already installed are
-not included in this list."
+not included in this list.
+
+SEEN is used internally to detect infinite recursion."
;; FIXME: We really should use backtracking to explore the whole
;; search space (e.g. if foo require bar-1.3, and bar-1.4 requires toto-1.1
;; whereas bar-1.3 requires toto-1.0 and the user has put a hold on toto-1.0:
@@ -893,15 +895,22 @@
(dolist (pkg packages)
(if (eq next-pkg (package-desc-name pkg))
(setq already pkg)))
- (cond
- (already
+ (when already
(if (version-list-<= next-version (package-desc-version already))
- ;; Move to front, so it gets installed early enough (bug#14082).
- (setq packages (cons already (delq already packages)))
+ ;; `next-pkg' is already in `packages', but its position there
+ ;; means it might be installed too late: remove it from there, so
+ ;; we re-add it (along with its dependencies) at an earlier place
+ ;; below (bug#16994).
+ (if (memq already seen) ;Avoid inf-loop on dependency cycles.
+ (message "Dependency cycle going through %S"
+ (package-desc-full-name already))
+ (setq packages (delq already packages))
+ (setq already nil))
(error "Need package `%s-%s', but only %s is being installed"
next-pkg (package-version-join next-version)
(package-version-join (package-desc-version already)))))
-
+ (cond
+ (already nil)
((package-installed-p next-pkg next-version) nil)
(t
@@ -933,12 +942,13 @@
(t (setq found pkg-desc)))))
(unless found
(if problem
- (error problem)
+ (error "%s" problem)
(error "Package `%s-%s' is unavailable"
next-pkg (package-version-join next-version))))
(setq packages
(package-compute-transaction (cons found packages)
- (package-desc-reqs found))))))))
+ (package-desc-reqs found)
+ (cons found seen))))))))
packages)
(defun package-read-from-string (str)
--- End Message ---