* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. [not found] ` <E1YLalx-0002s8-E8@vcs.savannah.gnu.org> @ 2015-02-11 19:28 ` Stefan Monnier 2015-02-11 23:00 ` Artur Malabarba 0 siblings, 1 reply; 9+ messages in thread From: Stefan Monnier @ 2015-02-11 19:28 UTC (permalink / raw) To: emacs-devel; +Cc: Artur Malabarba > + ((not (package--compatible-p pkg-desc)) "incompat") Of course, this should be transitive: if one of the required packages is "incompat", then the package is also "incompat". Stefan ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-11 19:28 ` [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages Stefan Monnier @ 2015-02-11 23:00 ` Artur Malabarba 2015-02-12 14:41 ` Stefan Monnier 0 siblings, 1 reply; 9+ messages in thread From: Artur Malabarba @ 2015-02-11 23:00 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 522 bytes --] > > + ((not (package--compatible-p pkg-desc)) "incompat") > > Of course, this should be transitive: if one of the required packages is > "incompat", then the package is also "incompat". Ideally, yes. That's why I factored it out as a function. However, this is called on each package about to be printed, and checking whether the dependencies are available imposes a performance cost that I'm not sure we should pay. The time for printing the package list will go from linear to quadratic in the number of packages. [-- Attachment #2: Type: text/html, Size: 653 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-11 23:00 ` Artur Malabarba @ 2015-02-12 14:41 ` Stefan Monnier 2015-02-12 16:35 ` Davis Herring 2015-02-12 21:42 ` chad 0 siblings, 2 replies; 9+ messages in thread From: Stefan Monnier @ 2015-02-12 14:41 UTC (permalink / raw) To: Artur Malabarba; +Cc: emacs-devel >> > + ((not (package--compatible-p pkg-desc)) "incompat") >> Of course, this should be transitive: if one of the required packages is >> "incompat", then the package is also "incompat". > Ideally, yes. That's why I factored it out as a function. > However, this is called on each package about to be printed, and checking > whether the dependencies are available imposes a performance cost that I'm > not sure we should pay. The time for printing the package list will go from > linear to quadratic in the number of packages. I understand, I was just pointing out that this current solution is incomplete. I expect that it's sufficient for now. The algorithmic problem is quite real, indeed. We could solve it by adding a "compatible" field to the struct, which we'd set to `yes' or `no' (so as to memoize previous computations), so the complexity would stay linear in the number of packages (though also linear in the number of number of `requires'). Stefan ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-12 14:41 ` Stefan Monnier @ 2015-02-12 16:35 ` Davis Herring 2015-02-13 13:48 ` Artur Malabarba 2015-02-12 21:42 ` chad 1 sibling, 1 reply; 9+ messages in thread From: Davis Herring @ 2015-02-12 16:35 UTC (permalink / raw) To: Stefan Monnier; +Cc: Artur Malabarba, emacs-devel > The algorithmic problem is quite real, indeed. > We could solve it by adding a "compatible" field to the struct, which > we'd set to `yes' or `no' (so as to memoize previous computations), so > the complexity would stay linear in the number of packages (though also > linear in the number of number of `requires'). The compatible flag need not be added to the struct; it could instead be maintained in a hash table retained only for the duration of printing. (Then it has to be recomputed once per listing, but as it's linear that probably doesn't matter.) Davis -- This product is sold by volume, not by mass. If it appears too dense or too sparse, it is because mass-energy conversion has occurred during shipping. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-12 16:35 ` Davis Herring @ 2015-02-13 13:48 ` Artur Malabarba 0 siblings, 0 replies; 9+ messages in thread From: Artur Malabarba @ 2015-02-13 13:48 UTC (permalink / raw) To: Davis Herring; +Cc: Stefan Monnier, emacs-devel 2015-02-12 16:35 GMT+00:00 Davis Herring <herring@lanl.gov>: >> The algorithmic problem is quite real, indeed. >> We could solve it by adding a "compatible" field to the struct, which >> we'd set to `yes' or `no' (so as to memoize previous computations), so >> the complexity would stay linear in the number of packages (though also >> linear in the number of number of `requires'). > > The compatible flag need not be added to the struct; it could instead be > maintained in a hash table retained only for the duration of printing. > (Then it has to be recomputed once per listing, but as it's linear that > probably doesn't matter.) I've just pushed an initial implementation of this. There is a hash table which lists the highest compatible version for each package (regardless of whether the package is installed or available). This compatibility is in the shallowest sense (the package's “emacs” dependency isn't higher than emacs-version). This table is populated in package-read-all-descriptors. Then, the package--incompatible-p function does the Emacs version checking and also checks the dependencies using the hashtable. This dependency checking is not recursive yet. The first step for making the dependency checking recursive (without making it quadratic) would be to store actual package-desc objects in the hash-table so their dependencies are immediately available (without having to find the object in the relevant alist). However, there is one obstacle that makes this non-trivial: - Package A-1.0 depends on B-1.0 which depends on C-1.0. - There's a new available version B-2.0 which depends on an incompatible version of C-2.0. - B-1.0 and C-1.0 are installed (and compatible). - Therefore, package A-1.0 can be installed (is compatible). In the current implementation, everything works: - The hashtable will store: [(A 1.0) (B 2.0) (C 1.0)] (remember, the hashtable only stores a shallow check). - The function package--incompatible-p (this is what does the full check) will correctly indicate B-2.0 and C-2.0 are NOT compatible, and correctly indicate A-1.0, B-1.0, and C-1.0 are all compatible. It works because A-1.0's only dependency is met in the hashtable (by B-2.0). On the other hand, if we naively make package--incompatible-p check deps recursively, then A-1.0's check will fail because B-2.0 fails. The perfect answer to this would be for the hashtable to only store fully compatible packages (so it would store B-1.0 instead of B-2.0), but I can't figure out a way to do that while keeping the hashtable build algorithm linear in the number of packages. The hashtable rebuilds every time the package list is refreshed, so I'd rather not make it quadratic, but maybe that's not a huge deal. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-12 14:41 ` Stefan Monnier 2015-02-12 16:35 ` Davis Herring @ 2015-02-12 21:42 ` chad 2015-02-13 20:13 ` Stefan Monnier 1 sibling, 1 reply; 9+ messages in thread From: chad @ 2015-02-12 21:42 UTC (permalink / raw) To: emacs-devel > On 12 Feb 2015, at 06:41, Stefan Monnier <monnier@iro.umontreal.ca> wrote: >>> >> Ideally, yes. That's why I factored it out as a function. >> However, this is called on each package about to be printed, and checking >> whether the dependencies are available imposes a performance cost that I'm >> not sure we should pay. The time for printing the package list will go from >> linear to quadratic in the number of packages. > > I understand, I was just pointing out that this current solution > is incomplete. I expect that it's sufficient for now. […] We could also make the recursive check happen only package.el tries to do anything with a specific package (package-menu-mark-*, package-menu-describe-package, etc). I don’t know if that’s better or not. ~Chad ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-12 21:42 ` chad @ 2015-02-13 20:13 ` Stefan Monnier 2015-02-13 20:18 ` Artur Malabarba 0 siblings, 1 reply; 9+ messages in thread From: Stefan Monnier @ 2015-02-13 20:13 UTC (permalink / raw) To: chad; +Cc: emacs-devel > We could also make the recursive check happen only package.el tries > to do anything with a specific package (package-menu-mark-*, > package-menu-describe-package, etc). I don’t know if that’s better or > not. Maybe you're right. Just like installation may fail because a dependency is missing. Maybe marking those things as uninstallable/incompatible is good, but only if we can explain concisely/easily enough to the user why it's uninstallable/incompatible. Stefan ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-13 20:13 ` Stefan Monnier @ 2015-02-13 20:18 ` Artur Malabarba 2015-02-14 18:04 ` Artur Malabarba 0 siblings, 1 reply; 9+ messages in thread From: Artur Malabarba @ 2015-02-13 20:18 UTC (permalink / raw) To: Stefan Monnier; +Cc: chad, emacs-devel [-- Attachment #1: Type: text/plain, Size: 461 bytes --] > Maybe you're right. Just like installation may fail because > a dependency is missing. Maybe marking those things as > uninstallable/incompatible is good, but only if we can explain > concisely/easily enough to the user why it's uninstallable/incompatible. Yes, it would be good to add that to the describe package buffer. package--incompatible-p already returns the reason why the package is incompatible, so it's just a matter of formating and printing. [-- Attachment #2: Type: text/html, Size: 538 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages. 2015-02-13 20:18 ` Artur Malabarba @ 2015-02-14 18:04 ` Artur Malabarba 0 siblings, 0 replies; 9+ messages in thread From: Artur Malabarba @ 2015-02-14 18:04 UTC (permalink / raw) To: Stefan Monnier; +Cc: chad, emacs-devel [-- Attachment #1: Type: text/plain, Size: 568 bytes --] On 13 Feb 2015 20:18, "Artur Malabarba" <bruce.connor.am@gmail.com> wrote: > > > Maybe you're right. Just like installation may fail because > > a dependency is missing. Maybe marking those things as > > uninstallable/incompatible is good, but only if we can explain > > concisely/easily enough to the user why it's uninstallable/incompatible. > > Yes, it would be good to add that to the describe package buffer. package--incompatible-p already returns the reason why the package is incompatible, so it's just a matter of formating and printing. This is now done. [-- Attachment #2: Type: text/html, Size: 749 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2015-02-14 18:04 UTC | newest] Thread overview: 9+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- [not found] <20150211170820.10979.16862@vcs.savannah.gnu.org> [not found] ` <E1YLalx-0002s8-E8@vcs.savannah.gnu.org> 2015-02-11 19:28 ` [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages Stefan Monnier 2015-02-11 23:00 ` Artur Malabarba 2015-02-12 14:41 ` Stefan Monnier 2015-02-12 16:35 ` Davis Herring 2015-02-13 13:48 ` Artur Malabarba 2015-02-12 21:42 ` chad 2015-02-13 20:13 ` Stefan Monnier 2015-02-13 20:18 ` Artur Malabarba 2015-02-14 18:04 ` Artur Malabarba
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.