From debbugs-submit-bounces@debbugs.gnu.org Wed Mar 12 02:25:28 2014 Received: (at submit) by debbugs.gnu.org; 12 Mar 2014 06:25:29 +0000 Received: from localhost ([127.0.0.1]:33803 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WNcbW-0007Mk-8g for submit@debbugs.gnu.org; Wed, 12 Mar 2014 02:25:28 -0400 Received: from eggs.gnu.org ([208.118.235.92]:50263) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WNafW-0003lu-PM for submit@debbugs.gnu.org; Wed, 12 Mar 2014 00:21:27 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WNafR-000409-7a for submit@debbugs.gnu.org; Wed, 12 Mar 2014 00:21:26 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50,T_MANY_HDRS_LCASE autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:56874) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WNafR-000405-4S for submit@debbugs.gnu.org; Wed, 12 Mar 2014 00:21:21 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:51962) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WNafL-0000Mz-L8 for bug-gnu-emacs@gnu.org; Wed, 12 Mar 2014 00:21:21 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WNafG-0003z5-F4 for bug-gnu-emacs@gnu.org; Wed, 12 Mar 2014 00:21:15 -0400 Received: from smtp4.clear.net.nz ([203.97.37.64]:34651) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WNafG-0003yp-2T for bug-gnu-emacs@gnu.org; Wed, 12 Mar 2014 00:21:10 -0400 Received: from mxin2-orange.clear.net.nz (lb2-srcnat.clear.net.nz [203.97.32.237]) by smtp4.clear.net.nz (CLEAR Net Mail) with ESMTP id <0N2B00KSK1CX9T70@smtp4.clear.net.nz> for bug-gnu-emacs@gnu.org; Wed, 12 Mar 2014 16:50:59 +1300 (NZDT) Received: from 202-78-141-194.cable.telstraclear.net (HELO mail.cons.org.nz) ([202.78.141.194]) by smtpin2.clear.net.nz with ESMTP; Wed, 12 Mar 2014 16:50:58 +1300 Received: from northind.cons.org.nz (northind.cons.org.nz [IPv6:2001:4428:27c:1::25]) by mail.cons.org.nz (Postfix) with ESMTP id 5B69327F191 for ; Wed, 12 Mar 2014 16:50:57 +1300 (NZDT) Received: by northind.cons.org.nz (Postfix, from userid 1001) id E44B384; Wed, 12 Mar 2014 16:50:56 +1300 (NZDT) Date: Wed, 12 Mar 2014 16:50:56 +1300 From: Andrew Childs Subject: 24.3; package.el dependency ordering incorrect (non-topological) To: bug-gnu-emacs@gnu.org Message-id: <86ha742hy7.fsf@northind.cons.org.nz> MIME-version: 1.0 Content-type: text/plain X-detected-operating-system: by eggs.gnu.org: Solaris 10 X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Wed, 12 Mar 2014 02:25:22 -0400 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) 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 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) From debbugs-submit-bounces@debbugs.gnu.org Tue May 06 14:13:55 2014 Received: (at 16994-done) by debbugs.gnu.org; 6 May 2014 18:13:55 +0000 Received: from localhost ([127.0.0.1]:53089 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WhjsI-0007Ho-UI for submit@debbugs.gnu.org; Tue, 06 May 2014 14:13:55 -0400 Received: from ironport2-out.teksavvy.com ([206.248.154.181]:35217) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WhjsG-0007Hb-IN for 16994-done@debbugs.gnu.org; Tue, 06 May 2014 14:13:53 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArYGAIDvNVO4rwut/2dsb2JhbABZgwaDSr0vgw6BFxd0giUBAQEBAgFWIwULCw4mEhQYDSSIBAjSGReOegeEOASUYgEFlDGBaoNMIQ X-IPAS-Result: ArYGAIDvNVO4rwut/2dsb2JhbABZgwaDSr0vgw6BFxd0giUBAQEBAgFWIwULCw4mEhQYDSSIBAjSGReOegeEOASUYgEFlDGBaoNMIQ X-IronPort-AV: E=Sophos;i="4.97,753,1389762000"; d="scan'208";a="61664387" Received: from 184-175-11-173.dsl.teksavvy.com (HELO pastel.home) ([184.175.11.173]) by ironport2-out.teksavvy.com with ESMTP/TLS/ADH-AES256-SHA; 06 May 2014 14:13:45 -0400 Received: by pastel.home (Postfix, from userid 20848) id 890EF60118; Tue, 6 May 2014 14:13:45 -0400 (EDT) From: Stefan Monnier To: Andrew Childs Subject: Re: bug#16994: 24.3; package.el dependency ordering incorrect (non-topological) Message-ID: References: <86ha742hy7.fsf@northind.cons.org.nz> Date: Tue, 06 May 2014 14:13:45 -0400 In-Reply-To: <86ha742hy7.fsf@northind.cons.org.nz> (Andrew Childs's message of "Wed, 12 Mar 2014 16:50:56 +1300") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.3 (/) X-Debbugs-Envelope-To: 16994-done Cc: 16994-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.3 (/) > 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) From unknown Sun Jun 15 08:51:33 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Wed, 04 Jun 2014 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator