From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp0.migadu.com ([2001:41d0:403:4876::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms13.migadu.com with LMTPS id gBQ6NuKnF2eoIAAAqHPOHw:P1 (envelope-from ) for ; Tue, 22 Oct 2024 13:25:55 +0000 Received: from aspmx1.migadu.com ([2001:41d0:403:4876::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp0.migadu.com with LMTPS id gBQ6NuKnF2eoIAAAqHPOHw (envelope-from ) for ; Tue, 22 Oct 2024 15:25:55 +0200 X-Envelope-To: larch@yhetil.org Authentication-Results: aspmx1.migadu.com; dkim=pass header.d=debbugs.gnu.org header.s=debbugs-gnu-org header.b=SYKjwSq3; dkim=fail ("headers rsa verify failed") header.d=gnu.org header.s=fencepost-gnu-org header.b=ERI0yGBU; dmarc=pass (policy=none) header.from=gnu.org; spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org" ARC-Seal: i=1; s=key1; d=yhetil.org; t=1729603554; a=rsa-sha256; cv=none; b=WniQyMOT9Rlzx04ZWEcMtGuf78/sxd65/2RybPCxB0jOwK1Y8Q5L/WTLSEv1GkpTDRynfy bE2ZbVuSlpnyKmkDJBtnzscB2NobuTjsXjr+ERWihNPT951Qk0i0qCFNsHbwVYyX9Fm8m7 kJM2BtAeL+JZisTMcgozV8q5ZufKMzDPocfUbLsx/NtNrcP02bh/asLvSzmLuaAMgXnod/ NJ4xUE1M4AByrO095n6XIQ8xd5J3CP55uDPb9GhG66y+O7PmS1ttlzgBb8E0UY/icicHQe acsmzbgccvhrPLOJCm7qaP8WBFPgSVXcOWSOdb/uIHpbOoOpZM7LeNNpx/17lA== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=debbugs.gnu.org header.s=debbugs-gnu-org header.b=SYKjwSq3; dkim=fail ("headers rsa verify failed") header.d=gnu.org header.s=fencepost-gnu-org header.b=ERI0yGBU; dmarc=pass (policy=none) header.from=gnu.org; spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org" ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1729603554; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:resent-cc: resent-from:resent-sender:resent-message-id:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post:dkim-signature; bh=qRpQMrJMJvuB1Ddne9oUw/ktsevOErvLmwhuqfaWleM=; b=QDMxKQCGdNoCSUyRvPOTOn08CWBvLkLQLF9UykdhSJIvuKWK2ZFhmi2H0Ln2CyhMHxTPvi yfW5xGSclZpjKRIsj7scmKF5Sa27AKx4pg9/YG1+L9/jTBPUxtNR5JqH5kkZVHt7HrbdMA 6LNpOU13AFV/lSHXkaGPW3CiO7vA0Nw7mtHlp3+XvmRevPzgbKrYvHC0D4nQPYeoQ3nLnp otgwG8JdLtd2sACSzjuGRhpxvInZrAZdiyDXdB+c6uymERmiGtnGKl72prIUWPtMr3Yb5C C7wXpZgMgSoKPSvYuNlwLCyjby6aywU8IyBp/ULoGlHIl3x+UGiilRENf6uvwQ== Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 6F9B337D81 for ; Tue, 22 Oct 2024 15:25:54 +0200 (CEST) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1t3EtN-0002wk-B8; Tue, 22 Oct 2024 09:25:45 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t3EtJ-0002wH-0b for guix-patches@gnu.org; Tue, 22 Oct 2024 09:25:41 -0400 Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1t3EtF-0007FP-4K; Tue, 22 Oct 2024 09:25:40 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=debbugs.gnu.org; s=debbugs-gnu-org; h=MIME-Version:References:In-Reply-To:Date:From:To:Subject; bh=qRpQMrJMJvuB1Ddne9oUw/ktsevOErvLmwhuqfaWleM=; b=SYKjwSq3qykmHF/CSc9CaZ+e/NU61B09btKFhIF4ZgyJiwz37NmTKL3W7Hl5g0TuDZZq6Tm+N3lnWtU7/739llkvCRG2Q2WhtPOAspvplv7+9jbH7/ehRyaUfcJVJG7fDGSgCR8AqAcJqC798dx2S9EGz8HT6fK2s29w3fdChSyHyBY+xm3Ny5hjxjOwRKHgDyrIg74huFwqetNmgTzGMlTGrFwV/KT/NmyrhOyhoCGYpDPQm1AhA/ucja3xzqWDmGb9l/1lA7gtdYaI+y0aN8uMaQ8HhEdY/9kd9W78beLAfSdBODc/zyL2WqOtmWLjIs4SdXu3QJjfqQYd9l/Mdg==; Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1t3Etd-0002xr-VP; Tue, 22 Oct 2024 09:26:02 -0400 X-Loop: help-debbugs@gnu.org Subject: [bug#73948] [PATCH 1/2] derivations: =?UTF-8?Q?=E2=80=98derivation-build-plan=E2=80=99?= returns builds in topological order. Resent-From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Original-Sender: "Debbugs-submit" Resent-CC: guix@cbaines.net, dev@jpoiret.xyz, ludo@gnu.org, othacehe@gnu.org, zimon.toutoune@gmail.com, me@tobias.gr, guix-patches@gnu.org Resent-Date: Tue, 22 Oct 2024 13:26:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73948 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: 73948@debbugs.gnu.org Cc: Ludovic =?UTF-8?Q?Court=C3=A8s?= , Christopher Baines , Josselin Poiret , Ludovic =?UTF-8?Q?Court=C3=A8s?= , Mathieu Othacehe , Simon Tournier , Tobias Geerinckx-Rice X-Debbugs-Original-Xcc: Christopher Baines , Josselin Poiret , Ludovic =?UTF-8?Q?Court=C3=A8s?= , Mathieu Othacehe , Simon Tournier , Tobias Geerinckx-Rice Received: via spool by 73948-submit@debbugs.gnu.org id=B73948.172960350910611 (code B ref 73948); Tue, 22 Oct 2024 13:26:01 +0000 Received: (at 73948) by debbugs.gnu.org; 22 Oct 2024 13:25:09 +0000 Received: from localhost ([127.0.0.1]:55054 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t3Esm-0002ka-Gh for submit@debbugs.gnu.org; Tue, 22 Oct 2024 09:25:09 -0400 Received: from eggs.gnu.org ([209.51.188.92]:49048) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t3Esk-0002hu-Qh for 73948@debbugs.gnu.org; Tue, 22 Oct 2024 09:25:07 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t3Eq6-0006wW-BO; Tue, 22 Oct 2024 09:22:22 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-Version:References:In-Reply-To:Date:Subject:To: From; bh=qRpQMrJMJvuB1Ddne9oUw/ktsevOErvLmwhuqfaWleM=; b=ERI0yGBUzd3uB5XSSJnv hb8E0a3NbCcUAZaUWR3erZkn8R2AV/s8xMq5aXDDKdqnzo0NJgJXIwHZVrqnWoDAIX2mPCY4anagA IbtGjZABu8r6Q8t4473PQ8g2zxwE5+evwdrPl+8hUf5GSeErCXiJefN7/QmtqS2VkzLn+mxMUWlBf FdilMLiXYL+I7lHlab4Qmk/K48r5qbUrqsgkusnmjKpG/5a5iYu4GgxnqYeUx3rjTdC/CD2SF3ZY7 KpZK7Jnz1pSJhJyKSnFYEQ63fHUGGi9lDLIETVFqhtFe1Xc+wrEO8PAvnJr72LcTHE/8OTKJz0bQ/ GbR7SW/9GkjRrw==; From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Date: Tue, 22 Oct 2024 15:22:09 +0200 Message-ID: X-Mailer: git-send-email 2.46.0 In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: guix-patches-bounces+larch=yhetil.org@gnu.org X-Migadu-Country: US X-Migadu-Flow: FLOW_IN X-Migadu-Spam-Score: -1.24 X-Spam-Score: -1.24 X-Migadu-Queue-Id: 6F9B337D81 X-Migadu-Scanner: mx10.migadu.com X-TUID: Mav2WajE654F That makes ‘derivation-build-plan’ directly usable in cases where one wants to sequentially build derivations one by one, or to report builds in the right order in the user interface. * guix/derivations.scm (derivation-build-plan): Wrap ‘loop’ in ‘traverse’. Perform a depth-first traversal. Return the list of builds in topological order. * tests/derivations.scm ("derivation-build-plan, topological ordering"): New test. Change-Id: I7cd9083f42c4381b4213794a40dbb5b234df966d --- guix/derivations.scm | 74 +++++++++++++++++++++++++------------------ tests/derivations.scm | 31 ++++++++++++++++-- 2 files changed, 72 insertions(+), 33 deletions(-) diff --git a/guix/derivations.scm b/guix/derivations.scm index a91c1ae984..bef98cd26a 100644 --- a/guix/derivations.scm +++ b/guix/derivations.scm @@ -401,8 +401,8 @@ (define* (derivation-build-plan store inputs (substitution-oracle store inputs #:mode mode))) "Given INPUTS, a list of derivation-inputs, return two values: the list of -derivations to build, and the list of substitutable items that, together, -allow INPUTS to be realized. +derivations to build, in topological order, and the list of substitutable +items that, together, allow INPUTS to be realized. SUBSTITUTABLE-INFO must be a one-argument procedure similar to that returned by 'substitution-oracle'." @@ -422,36 +422,48 @@ (define* (derivation-build-plan store inputs (and (= (length info) (length items)) info)))) - (let loop ((inputs inputs) ;list of - (build '()) ;list of - (substitute '()) ;list of - (visited (set))) ;set of - (match inputs - (() - (values build substitute)) - ((input rest ...) - (let ((key (derivation-input-key input)) - (deps (derivation-inputs - (derivation-input-derivation input)))) - (cond ((set-contains? visited key) - (loop rest build substitute visited)) - ((input-built? input) - (loop rest build substitute - (set-insert key visited))) - ((input-substitutable-info input) - => - (lambda (substitutables) - (loop (append (dependencies-of-substitutables substitutables + (define (traverse) + ;; Perform a depth-first traversal. + (let loop ((inputs inputs) ;list of + (build '()) ;list of + (substitute '()) ;list of + (visited (set))) ;set of + (match inputs + (() + (values visited build substitute)) + ((input rest ...) + (let ((key (derivation-input-key input)) + (deps (derivation-inputs + (derivation-input-derivation input)))) + (cond ((set-contains? visited key) + (loop rest build substitute visited)) + ((input-built? input) + (loop rest build substitute (set-insert key visited))) + ((input-substitutable-info input) + => + (lambda (substitutables) + (call-with-values + (lambda () + (loop (dependencies-of-substitutables substitutables deps) - rest) - build - (append substitutables substitute) - (set-insert key visited)))) - (else - (loop (append deps rest) - (cons (derivation-input-derivation input) build) - substitute - (set-insert key visited))))))))) + build + (append substitutables substitute) + (set-insert key visited))) + (lambda (visited build substitute) + (loop rest build substitute visited))))) + (else + (call-with-values + (lambda () + (loop deps build substitute (set-insert key visited))) + (lambda (visited build substitute) + (loop rest + (cons (derivation-input-derivation input) build) + substitute + visited)))))))))) + + (call-with-values traverse + (lambda (_ build substitute) + (values (reverse! build) substitute)))) (define-deprecated (derivation-prerequisites-to-build store drv #:rest rest) derivation-build-plan diff --git a/tests/derivations.scm b/tests/derivations.scm index 0e87778981..efcd21f324 100644 --- a/tests/derivations.scm +++ b/tests/derivations.scm @@ -1,5 +1,5 @@ ;;; GNU Guix --- Functional package management for GNU -;;; Copyright © 2012-2023 Ludovic Courtès +;;; Copyright © 2012-2024 Ludovic Courtès ;;; ;;; This file is part of GNU Guix. ;;; @@ -29,7 +29,8 @@ (define-module (test-derivations) #:use-module (guix tests git) #:use-module (guix tests http) #:use-module ((guix packages) #:select (package-derivation base32)) - #:use-module ((guix build utils) #:select (executable-file?)) + #:use-module ((guix build utils) + #:select (executable-file? strip-store-file-name)) #:use-module ((guix hash) #:select (file-hash*)) #:use-module ((git oid) #:select (oid->string)) #:use-module ((git reference) #:select (reference-name->oid)) @@ -1157,6 +1158,32 @@ (define %coreutils #:mode (build-mode check)) (list drv dep)))))) +(test-equal "derivation-build-plan, topological ordering" + (make-list 5 '("0.drv" "1.drv" "2.drv" "3.drv" "4.drv")) + (with-store store + (define (test _) + (let* ((simple-derivation + (lambda (name . deps) + (build-expression->derivation + store name + `(begin ,(random-text) (mkdir %output)) + #:inputs (map (lambda (n dep) + (list (number->string n) dep)) + (iota (length deps)) + deps)))) + (drv0 (simple-derivation "0")) + (drv1 (simple-derivation "1" drv0)) + (drv2 (simple-derivation "2" drv1)) + (drv3 (simple-derivation "3" drv2 drv0)) + (drv4 (simple-derivation "4" drv3 drv1))) + (map (compose strip-store-file-name derivation-file-name) + (derivation-build-plan store (list (derivation-input drv4)))))) + + ;; This is probabilistic: if the traversal is buggy, it may or may not + ;; produce the wrong ordering, depending on a variety of actors. Thus, + ;; try multiple times. + (map test (iota 5)))) + (test-assert "derivation-input-fold" (let* ((builder (add-text-to-store %store "my-builder.sh" "echo hello, world > \"$out\"\n" -- 2.46.0