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

[Artur Malabarba <bruce.connor.am@gmail.com>]

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.