Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Stefan Monnier]

> +     ((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

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Artur Malabarba]

[-- 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 --]

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Stefan Monnier]

>> > +     ((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

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Davis Herring]

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

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Artur Malabarba]

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.

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[chad]

> 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

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Stefan Monnier]

> 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

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Artur Malabarba]

[-- 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 --]

Re: [Emacs-diffs] scratch/package-fix e5d5cdf 1/2: emacs-lisp/package.el: Indicate incompatible packages.

[Artur Malabarba]

[-- 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 --]