From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp10.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id AAalDqos9GEg8QAAgWs5BA (envelope-from ) for ; Fri, 28 Jan 2022 18:49:30 +0100 Received: from aspmx1.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp10.migadu.com with LMTPS id iMR0B6os9GGASwAAG6o9tA (envelope-from ) for ; Fri, 28 Jan 2022 18:49:30 +0100 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 9728F3E749 for ; Fri, 28 Jan 2022 18:49:29 +0100 (CET) Received: from localhost ([::1]:34238 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nDVNI-0003H5-AI for larch@yhetil.org; Fri, 28 Jan 2022 12:49:28 -0500 Received: from eggs.gnu.org ([209.51.188.92]:34796) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nDVI5-0001F7-5Q for guix-patches@gnu.org; Fri, 28 Jan 2022 12:44:05 -0500 Received: from debbugs.gnu.org ([209.51.188.43]:39296) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nDVI4-0001am-6I for guix-patches@gnu.org; Fri, 28 Jan 2022 12:44:04 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nDVI3-0001D0-05 for guix-patches@gnu.org; Fri, 28 Jan 2022 12:44:03 -0500 X-Loop: help-debbugs@gnu.org Subject: [bug#53608] [PATCH 1/2] git: Add 'commit-descendant?'. References: <20220128173142.7072-1-ludo@gnu.org> In-Reply-To: <20220128173142.7072-1-ludo@gnu.org> Resent-From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Fri, 28 Jan 2022 17:44:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 53608 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: 53608@debbugs.gnu.org Cc: Ludovic =?UTF-8?Q?Court=C3=A8s?= Received: via spool by 53608-submit@debbugs.gnu.org id=B53608.16433918084560 (code B ref 53608); Fri, 28 Jan 2022 17:44:02 +0000 Received: (at 53608) by debbugs.gnu.org; 28 Jan 2022 17:43:28 +0000 Received: from localhost ([127.0.0.1]:60425 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nDVHU-0001BU-4C for submit@debbugs.gnu.org; Fri, 28 Jan 2022 12:43:28 -0500 Received: from eggs.gnu.org ([209.51.188.92]:33924) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nDVHS-0001B9-9L for 53608@debbugs.gnu.org; Fri, 28 Jan 2022 12:43:26 -0500 Received: from [2001:470:142:3::e] (port=33974 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nDVHH-0001Xj-WB; Fri, 28 Jan 2022 12:43:19 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-Version:Date:Subject:To:From:in-reply-to: references; bh=keTnlh4PjmKHkmyLkF5P2cbYzw/gceW7Tj9wAidp2hA=; b=FbyAP0rtJCBRBX MGPaScgbTcyZ9+PikHnLbLkIMvA9lweF0aebUknY4lfiF158VahRmpwDrnuETheHVBbsObH8ZDNSl vDecFyrP2y2YOy5PhYQec8OFz9j8asFcjivt6ZTvRtw2FOdlV4q5qZiQnaDuDOxyIuiPVK0LqV4K0 bq6B6HkI4W4jlYYFHkKwsdrU6C62QCQhNRTcx8ksrGwlybouxmnKReErN094uLuNaxqqnd+xKFbpr ENTSdR/B2jV3pP/DyMFUVegJlGuCOOpYo5L4AiU+UVPLh8Io8kxT/U7WkI4UidjQGOR1bb3KG8Tsq yHJZJJXItV0vv0qWLeWw==; Received: from [2001:660:6102:320:e120:2c8f:8909:cdfe] (port=33810 helo=gnu.org) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nDVHC-0002VO-Qf; Fri, 28 Jan 2022 12:43:13 -0500 From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Date: Fri, 28 Jan 2022 18:43:00 +0100 Message-Id: <20220128174301.7632-1-ludo@gnu.org> X-Mailer: git-send-email 2.34.0 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" X-Migadu-Flow: FLOW_IN X-Migadu-Country: US ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1643392169; 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=FNAGFROfvNquhA0ZnWFy6NjuzGt/JDYqo5IoAJ5AcBI=; b=aCelEZ0Z5Ii7yLHI5RuLzQ9SAYfIG2vvM0piULA0K9bmPKzJoSgs9VFOTv9aVCVA6RMgbk 9nNC+eUxWSoTx6o1jgoNSP2kwqef0vLBETZnMr99aRSGZ+YEXsHkUHhrCSJ3YZcXX3K67Z EAO/b6HhXukh0kzAQ72wjdJhZVydFxf88GBB+z+SX5guAe8oiujBF26Syx2LTDSvTNEO8u Cjo6Tle7/AXujNehsDChAKz8JOpUXstJ0Ad6zI2NRtOKuYpoWBHtmRp8042dbmTn3a0Sm8 X1iFIKy4B4y3rfCAjIAMdIUDMKTjQnC990flsV/EzdQICyazqL1m0XHAHqI3TA== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1643392169; a=rsa-sha256; cv=none; b=hHeoBPK3Qc/XZZSDEID0lIVxurbTc6JQsd3nfHRpo5mw061yIIhZ5ptevt5W0WJ2P2ktat lMjQIuDLazYB6GzYv2J8seYQk6Od9xgCATePiqrpTQz4/KlPt2STK7sRmqAW0q75o8YtGA t/iEKac6sxD+/T5Wu53+4HtHQq7k1j2f757OW03DERUxZe21jsiVVMhM8jOyOSfTtF0gBp 9Miz1L/ubh0GYPFEo1u7P1m53DCW1noCeSPXNKFth3ch3kPX/XEVu/xBjSWpvvHJhN14vE cUo2gFEO/KZxA++SKNtnZTQ84pYB6yDhLrxMW1XBeql+3LTSDZCgaD4lCHlTCw== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=fail ("body hash did not verify") header.d=gnu.org header.s=fencepost-gnu-org header.b=FbyAP0rt; 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" X-Migadu-Spam-Score: -2.83 Authentication-Results: aspmx1.migadu.com; dkim=fail ("body hash did not verify") header.d=gnu.org header.s=fencepost-gnu-org header.b=FbyAP0rt; 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" X-Migadu-Queue-Id: 9728F3E749 X-Spam-Score: -2.83 X-Migadu-Scanner: scn1.migadu.com X-TUID: 3JCOpy70/ju3 * guix/git.scm (commit-descendant?): New procedure. * tests/git.scm ("commit-descendant?"): New test. --- guix/git.scm | 24 +++++++++++++++++++++++- tests/git.scm | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 74 insertions(+), 2 deletions(-) diff --git a/guix/git.scm b/guix/git.scm index 43e85a5026..53e7219c8c 100644 --- a/guix/git.scm +++ b/guix/git.scm @@ -1,6 +1,6 @@ ;;; GNU Guix --- Functional package management for GNU ;;; Copyright © 2017, 2020 Mathieu Othacehe -;;; Copyright © 2018, 2019, 2020, 2021 Ludovic Courtès +;;; Copyright © 2018-2022 Ludovic Courtès ;;; Copyright © 2021 Kyle Meyer ;;; Copyright © 2021 Marius Bakke ;;; Copyright © 2022 Maxime Devos @@ -46,6 +46,7 @@ (define-module (guix git) #:use-module (ice-9 ftw) #:use-module (srfi srfi-1) #:use-module (srfi srfi-11) + #:use-module (srfi srfi-26) #:use-module (srfi srfi-34) #:use-module (srfi srfi-35) #:export (%repository-cache-directory @@ -60,6 +61,7 @@ (define-module (guix git) latest-repository-commit commit-difference commit-relation + commit-descendant? remote-refs @@ -623,6 +625,26 @@ (define (commit-relation old new) (if (set-contains? oldest new) 'descendant 'unrelated)))))) + +(define (commit-descendant? new old) + "Return true if NEW is the descendant of one of OLD, a list of commits. + +When the expected result is likely #t, this is faster than using +'commit-relation' since fewer commits need to be traversed." + (let ((old (list->setq old))) + (let loop ((commits (list new)) + (visited (setq))) + (match commits + (() + #f) + (_ + ;; Perform a breadth-first search as this is likely going to + ;; terminate more quickly than a depth-first search. + (let ((commits (remove (cut set-contains? visited <>) commits))) + (or (any (cut set-contains? old <>) commits) + (loop (append-map commit-parents commits) + (fold set-insert visited commits))))))))) + ;; ;;; Remote operations. diff --git a/tests/git.scm b/tests/git.scm index d0646bbc85..ca59d2a33e 100644 --- a/tests/git.scm +++ b/tests/git.scm @@ -1,5 +1,5 @@ ;;; GNU Guix --- Functional package management for GNU -;;; Copyright © 2019, 2020 Ludovic Courtès +;;; Copyright © 2019, 2020, 2022 Ludovic Courtès ;;; Copyright © 2021 Xinglu Chen #t) + (master1 master3 => #f) + (master3 master1 => #t) + (master2 branch1 => #f) + (master2 branch1 master1 => #t) + (branch1 master2 => #f) + (branch1 merge => #f) + (merge branch1 => #t) + (master1 merge => #f) + (merge master1 => #t)) + (with-temporary-git-repository directory + '((add "a.txt" "A") + (commit "first commit") + (branch "hack") + (checkout "hack") + (add "1.txt" "1") + (commit "branch commit") + (checkout "master") + (add "b.txt" "B") + (commit "second commit") + (add "c.txt" "C") + (commit "third commit") + (merge "hack" "merge")) + (with-repository directory repository + (let ((master1 (find-commit repository "first")) + (master2 (find-commit repository "second")) + (master3 (find-commit repository "third")) + (branch1 (find-commit repository "branch")) + (merge (find-commit repository "merge"))) + (letrec-syntax ((verify + (syntax-rules () + ((_) '()) + ((_ (new old ...) rest ...) + (cons `(new old ... => + ,(commit-descendant? new + (list old ...))) + (verify rest ...)))))) + (verify (master3 master3) + (master1 master3) + (master3 master1) + (master2 branch1) + (master2 branch1 master1) + (branch1 master2) + (branch1 merge) + (merge branch1) + (master1 merge) + (merge master1))))))) + (unless (which (git-command)) (test-skip 1)) (test-equal "remote-refs" '("refs/heads/develop" "refs/heads/master" -- 2.34.0