[Emacs-diffs] emacs-24 r117075: * lisp/emacs-lisp/package.el (package-compute-transaction): Topological sort.

[Stefan Monnier]

------------------------------------------------------------
revno: 117075
revision-id: address@hidden
parent: address@hidden
fixes bug: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16994
committer: Stefan Monnier <address@hidden>
branch nick: emacs-24
timestamp: Tue 2014-05-06 14:11:16 -0400
message:
  * lisp/emacs-lisp/package.el (package-compute-transaction): Topological sort.
  Add optional `seen' argument to detect and break infinite loops.
modified:
  lisp/ChangeLog                 changelog-20091113204419-o5vbwnq5f7feedwu-1432
  lisp/emacs-lisp/package.el     package.el-20100617020707-ybavz666awsxwin6-2

=== modified file 'lisp/ChangeLog'
--- a/lisp/ChangeLog    2014-05-06 10:29:37 +0000
+++ b/lisp/ChangeLog    2014-05-06 18:11:16 +0000
@@ -1,3 +1,8 @@
+2014-05-06  Stefan Monnier  <address@hidden>
+
+       * emacs-lisp/package.el (package-compute-transaction): Topological sort.
+       Add optional `seen' argument to detect and break infinite loops.
+
 2014-05-06  Eli Zaretskii  <address@hidden>
 
        * emacs-lisp/find-gc.el (find-gc-unsafe, find-unsafe-funcs)
@@ -6,11 +11,11 @@
 
 2014-05-06  Michael Albinus  <address@hidden>
 
-       * net/tramp-sh.el (tramp-remote-process-environment): Remove
-       HISTFILE and HISTSIZE; it's too late to set them here.  Add
-       :version entry.
-       (tramp-open-shell): Do not let-bind `tramp-end-of-output'.  Add
-       "HISTSIZE=/dev/null" to the shell's env arguments.  Do not send
+       * net/tramp-sh.el (tramp-remote-process-environment):
+       Remove HISTFILE and HISTSIZE; it's too late to set them here.
+       Add :version entry.
+       (tramp-open-shell): Do not let-bind `tramp-end-of-output'.
+       Add "HISTSIZE=/dev/null" to the shell's env arguments.  Do not send
        extra "PSx=..." commands.
        (tramp-maybe-open-connection): Setenv HISTFILE to /dev/null.
        (Bug#17295)
@@ -126,8 +131,8 @@
        (todo-edit-done-item--param-key-alist): New defconsts.
        (todo-edit-item--prompt): New variable.
        (todo-edit-item--next-key): New function.
-       (todo-key-bindings-t): Bind "e" to todo-edit-item.  Remove
-       bindings of deleted commands.
+       (todo-key-bindings-t): Bind "e" to todo-edit-item.
+       Remove bindings of deleted commands.
 
 2014-05-02  Leo Liu  <address@hidden>
 

=== modified file 'lisp/emacs-lisp/package.el'
--- a/lisp/emacs-lisp/package.el        2014-03-28 22:47:46 +0000
+++ b/lisp/emacs-lisp/package.el        2014-05-06 18:11:16 +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)