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

[Andrew Childs]

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)