bug#61161: package-input-rewriting causes different ordering of grafts

[Akira Kyle <akira@akirakyle.com>]

I think this may be a strange, subtle bug and hopefully this is 
sufficient to reproduce.
This was all done with guix commit 
da9af8c72fe427e3eeb718b53c599139a8958d61.

Consider the following:

(use-modules (guix packages)
             (guix gexp)
             (guix monads)
             (guix store)
             (guix git)
             (guix download)
             (guix git-download)
             (gnu packages compression)
             (gnu packages emacs-xyz))

(define (package-commit pkg commit checksum)
  "Return a package variant using the given commit and sha256."
  (package
    (inherit pkg)
    (name (package-name pkg))
    (version (substring commit 0 7))
    (source
     (origin
       (method git-fetch)
       (uri (git-reference
             (url (git-checkout-url (git-reference->git-checkout
                                     (origin-uri (package-source 
                                     pkg)))))
             (commit commit)))
       (sha256 (base32 checksum))
       (file-name (git-file-name name version))))))

(define emacs-magit-latest 
  (package-commit emacs-magit
                  "45be64e5f1ef0d03156c53543eb198829177a934"
                  "19b1d4200x1rhffmxf834kh55nj2zjps09hkkhw9hrsdig3nlfl9"))

(define emacs-compat-latest
  (package
    (inherit emacs-compat)
    (version "29.1.3.0")
    (source (origin
              (method url-fetch)
              (uri (string-append "https://elpa.gnu.org/packages/"
                                  "compat-" version ".tar.lz"))
              (sha256
               (base32
                "0jnk81rg5w6zhf413nf3j72i2mr8vfdms55gahrdx28727w8gfj8"))))
    (native-inputs (modify-inputs (package-native-inputs 
    emacs-compat)
                         (prepend lzip)))))

(define with-replacements
  (package-input-rewriting `((,emacs-compat 
  . ,emacs-compat-latest))))


(list
 emacs-magit-latest
 (with-replacements emacs-magit-latest)
 )

emacs-magit-latest depends on
/gnu/store/xrwyv6s8gsazgb2hqxxvh3h6d9cvkxal-git-2.39.1.drv

whereas (with-replacements emacs-magit-latest)` depends on
/gnu/store/x2gd1dsqvpas4rwvlxdmj7p9w2d2ba49-git-2.39.1.drv

Which is surprising since I didn't change anything about the git 
package.

Following this a bit further reveals that the difference comes 
down to the grafts being applied to python where 
emacs-magit-latest depends on
/gnu/store/848hfdz4xj91jail0y8lfj22dkgb3d12-python-3.9.9-builder


whereas (with-replacements emacs-magit-latest)` depends on
/gnu/store/f3b6wlkwnnp2zfm20br6hbc9i0pipi24-python-3.9.9-builder


Inspecting these derivations, the difference between them seems to 
be that in the former has zlib first in the `mapping` field of the 
graft while in the latter zlib is last. My guess is this is due to 
the fact that the emacs-compat override adds lzip to its 
native-inputs and causes a different traversal order for grafting 
zlib. But this is my first time attempting to look at the grafting 
machinery in detail, so hopefully the experts can figure out if 
this really is a bug and how to fix it!

I don't have a concrete example where this causes issues in 
practice, since here the two packages would conflict anyways due 
to different compat versions, but it seems like that's mostly a 
consequence of emacs-packages having propagated dependencies. At 
the very least it would seem to cause unnecessary duplication in 
the store.