store: 'references/substitutes' correctly handles the order of substitutes.

Before that, 'references/substitutes' would assume that
'substitutable-path-info' would return things in the same order as its
arguments, which is not the case.  Thus, it would sometimes provide
incorrect reference information, occasionally leading to infinite
loop (because dependency information would denote cycles.)

Fixes <http://bugs.gnu.org/22914>.
Reported by Eric Bavier <ericbavier@openmailbox.org>.

* guix/store.scm (references/substitutes): Make ITEMS the first argument
of the loop; match on it.  Use 'any' to find a matching substitute.
(substitutable-path-info): Clarify docstring about ordering.

1 files changed, 18 insertions, 10 deletions

diff --git a/guix/store.scm b/guix/store.scm
index 56aa38ba8d..a220b6e6f9 100644
--- a/guix/store.scm
+++ b/guix/store.scm
@@ -752,18 +752,24 @@ the list of references")
                          (status 1)))))
 
     ;; Intersperse SUBSTS and LOCAL-REFS.
-    (let loop ((local-refs  local-refs)
-               (remote-refs (map substitutable-references substs))
+    (let loop ((items       items)
+               (local-refs  local-refs)
                (result      '()))
-      (match local-refs
+      (match items
         (()
          (reverse result))
-        ((#f tail ...)
-         (match remote-refs
-           ((remote rest ...)
-            (loop tail rest (cons remote result)))))
-        ((head tail ...)
-         (loop tail remote-refs (cons head result)))))))
+        ((item items ...)
+         (match local-refs
+           ((#f tail ...)
+            (loop items tail
+                  (cons (any (lambda (subst)
+                               (and (string=? (substitutable-path subst) item)
+                                    (substitutable-references subst)))
+                             substs)
+                        result)))
+           ((head tail ...)
+            (loop items tail
+                  (cons head result)))))))))
 
 (define* (fold-path store proc seed path
                     #:optional (relatives (cut references store <>)))
@@ -852,7 +858,9 @@ topological order."
   (operation (query-substitutable-path-infos (store-path-list paths))
              "Return information about the subset of PATHS that is
 substitutable.  For each substitutable path, a `substitutable?' object is
-returned."
+returned; thus, the resulting list can be shorter than PATHS.  Furthermore,
+that there is no guarantee that the order of the resulting list matches the
+order of PATHS."
              substitutable-path-list))
 
 (define-operation (optimize-store)