GNU bug report logs - #16994
24.3; package.el dependency ordering incorrect (non-topological)

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 16994 in the body.
You can then email your comments to 16994 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Andrew Childs <lorne <at> cons.org.nz>
To: bug-gnu-emacs <at> gnu.org
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)

Message #10 received at 16994-done <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Andrew Childs <lorne <at> cons.org.nz>
Cc: 16994-done <at> debbugs.gnu.org
Subject: Re: bug#16994: 24.3;
 package.el dependency ordering incorrect (non-topological)
Date: Tue, 06 May 2014 14:13:45 -0400

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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.