> Here the issue shows itself, `seq` is now requested for installation,
> which is incorrect, since Emacs already have the latest version.

TL;DR I believe I have found the bug in `package-compute-transaction'.
It misses the
assignment to the newer version of the package that was already in the list of
packages to be installed.


Some details. The following 1-line change fixes it for me (added context around
for readability), in `package-compute-transaction':

       (when already
         (if (version-list-<= next-version (package-desc-version already))
             ;; `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 next-version (package-desc-version already))
               (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)))))


The issue occurs in the following scenario:
    - Package A (version a), noted A(a), depends on packages B(z), then C(y)
    - Package C(y) depends on package B(x), which is an _older_
version than B(z)
    - Neither A(a), B(z) nor C(y) are installed (the state of B(x) is
irrelevant)

`package-compute-transaction' will consider first the requirement B(z) and push
it to PACKAGES; then the requirement C(y) is pushed. It will then consider
C(y)'s requirement B(x). Since B is ALREADY seen, it first deletes B(z) from
PACKAGES, expecting to push in front of PACKAGES later, in `cond''s body (so
that B is installed earlier than both A and C). **But it fails to set
NEXT-VERSION to the newer B(z) and retains B(x)'s older version instead.**
That's the edge-case of the bug.

The fix is to set NEXT-VERSION to the version of the equal or newer package,
which is always the one already present in PACKAGE, given the preceding `if'
condition.

In my case, this result in the strange disappearance of `seq' from PACKAGES when
`compat' is not installed, because the older version of `seq' is already
installed and it's enough to meet the requirement of one of the transitive
dependencies of `git-commit', which is `compat'. On the other end, if `compat'
is installed, it's requirements are not checked and thus `seq' remains in the
list.

I provided the format-patch for it in the attachment, but it's the
same single line
of code change as shown above. I have no knowledge on how to submit it other
than by this email, any guidance or direction is appreciated.



Though interestingly, that was actually not the root cause of my personal
problem. I didn't expect `seq' to be installed in the first place, it is
built-in and `package-install-upgrade-built-in' is `nil' on my setup. (I was
expecting to find an issue revolving around this, and stumbled on this one :) )

Do you think I have misunderstood the purpose of
`package-install-upgrade-built-in'? Should the `package-compute-transaction` be
fixed to take it into account? It is not too difficult to do, however I think
this would be a rather impacting change, as users may have gotten used to their
built-in packages dependencies being upgraded without friction, even when they
are built-in.

Looking for another opinion, I lack context on the purpose of
`package-install-upgrade-built-in`.

    - Sylvain