GNU bug report logs - #77875
[PATCH 0/2] Use 'graph-descendant?' from Guile-Git instead of custom code

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 77875 in the body.
You can then email your comments to 77875 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: guix-patches <at> gnu.org
Cc: Ludovic Courtès <ludo <at> gnu.org>,
 Tomas Volf <~@wolfsden.cz>
Subject: [PATCH 0/2] Use 'graph-descendant?' from Guile-Git instead of custom
 code
Date: Thu, 17 Apr 2025 22:19:58 +0200

Hello,

This is a bug fix and potentially a performance improvement (I didn’t
attempt to benchmark it but if someone wants to do it, I’m curious!).

Note that the existing code is kept around for now.  We can remove it
in a couple of months when Guile-Git 0.10.0 is considered widespread
enough.  This is a convenience for developers since in practice Guix
itself will have switched to Guile-Git 0.10.0 within a few hours.

Thanks,
Ludo’.

Ludovic Courtès (2):
  git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
  git: Remove compatibility shim for Guile-Git <= 0.5.2.

 guix/git.scm | 90 ++++++++++++++++++++++++++++++----------------------
 1 file changed, 52 insertions(+), 38 deletions(-)


base-commit: 4bd2949cfa7a8bf5dfe66adad1a76472af09708d
-- 
2.49.0

Message #8 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: 77875 <at> debbugs.gnu.org
Cc: Ludovic Courtès <ludo <at> gnu.org>,
 Tomas Volf <~@wolfsden.cz>
Subject: [PATCH 1/2] git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
Date: Thu, 17 Apr 2025 22:22:36 +0200

Fixes <https://issues.guix.gnu.org/66268>.

Fixes a bug whereby ‘commit-relation’ and ‘commit-descendant?’ would
provide an incorrect result when two distinct <commit> objects would
exist for the same commit, which can happen when the commit’s metadata
is beyond 4 KiB, as of libgit2 1.8/1.9.

This, in turn, would lead ‘guix pull’ & co. to wrongfully report an
attempt to downgrade and pull to an unrelated commit.

* guix/git.scm (commit-relation): When (guix graph) is available,
rewrite in terms of ‘graph-descendant?’.
(commit-descendant?): Likewise.

Change-Id: Ie52b188a8dfa90c95a73387c3ab2fdd04d2bf3e9
Reported-by: Tomas Volf <~@wolfsden.cz>
---
 guix/git.scm | 83 ++++++++++++++++++++++++++++++++--------------------
 1 file changed, 52 insertions(+), 31 deletions(-)

diff --git a/guix/git.scm b/guix/git.scm
index 01e0918588..cb26714d2d 100644
--- a/guix/git.scm
+++ b/guix/git.scm
@@ -732,7 +732,7 @@ (define (print-git-error port key args default-printer)
 ;;; Commit difference.
 ;;;
 
-(define* (commit-closure commit #:optional (visited (setq)))
+(define* (commit-closure commit #:optional (visited (setq))) ;to remove
   "Return the closure of COMMIT as a set.  Skip commits contained in VISITED,
 a set, and adjoin VISITED to the result."
   (let loop ((commits (list commit))
@@ -768,39 +768,60 @@ (define* (commit-difference new old #:optional (excluded '()))
                  (cons head result)
                  (set-insert head visited)))))))
 
-(define (commit-relation old new)
-  "Return a symbol denoting the relation between OLD and NEW, two commit
+(define commit-relation
+  (if (resolve-module '(guix graph) #:ensure #f)  ;Guile-Git >= 0.10.0
+      (lambda (old new)
+        "Return a symbol denoting the relation between OLD and NEW, two commit
 objects: 'ancestor (meaning that OLD is an ancestor of NEW), 'descendant, or
 'unrelated, or 'self (OLD and NEW are the same commit)."
-  (if (eq? old new)
-      'self
-      (let ((newest (commit-closure new)))
-        (if (set-contains? newest old)
-            'ancestor
-            (let* ((seen   (list->setq (commit-parents new)))
-                   (oldest (commit-closure old seen)))
-              (if (set-contains? oldest new)
-                  'descendant
-                  'unrelated))))))
+        (let ((repository (commit-owner old))
+              (old (commit-id old))
+              (new (commit-id new)))
+          (cond ((graph-descendant? repository new old)
+                 'ancestor)
+                ((oid=? old new)
+                 'self)
+                ((graph-descendant? repository old new)
+                 'descendant)
+                (else 'unrelated))))
+      (lambda (old new)            ;remove when Guile-Git 0.10.0 is widespread
+        (if (eq? old new)
+            'self
+            (let ((newest (commit-closure new)))
+              (if (set-contains? newest old)
+                  'ancestor
+                  (let* ((seen   (list->setq (commit-parents new)))
+                         (oldest (commit-closure old seen)))
+                    (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)))))))))
+(define commit-descendant?
+  (if (resolve-module '(guix graph) #:ensure #f)  ;Guile-Git >= 0.10.0
+      (lambda (new old)
+        "Return true if NEW is the descendant of one of OLD, a list of
+commits."
+        (let ((repository (commit-owner new))
+              (new (commit-id new)))
+          (any (lambda (old)
+                 (let ((old (commit-id old)))
+                   (or (graph-descendant? repository new old)
+                       (oid=? old new))))
+               old)))
+      (lambda (new old)            ;remove when Guile-Git 0.10.0 is widespread
+        (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)))))))))))
 
 
 ;;
-- 
2.49.0

Message #11 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: 77875 <at> debbugs.gnu.org
Cc: Ludovic Courtès <ludo <at> gnu.org>
Subject: [PATCH 2/2] git: Remove compatibility shim for Guile-Git <= 0.5.2.
Date: Thu, 17 Apr 2025 22:22:37 +0200

Guile-Git 0.5.2 was released in July 2021.

* guix/git.scm (GITERR_HTTP): Remove.

Change-Id: I05b2ee36f786bd83ca91c8989912f83f6dde59c0
---
 guix/git.scm | 7 -------
 1 file changed, 7 deletions(-)

diff --git a/guix/git.scm b/guix/git.scm
index cb26714d2d..2ff2bfd8ed 100644
--- a/guix/git.scm
+++ b/guix/git.scm
@@ -206,13 +206,6 @@ (define* (make-default-fetch-options #:key (verify-certificate? #t))
                                                  warn-for-invalid-certificate)))
     options))
 
-(define GITERR_HTTP
-  ;; Guile-Git <= 0.5.2 lacks this constant.
-  (let ((errors (resolve-interface '(git errors))))
-    (if (module-defined? errors 'GITERR_HTTP)
-        (module-ref errors 'GITERR_HTTP)
-        34)))
-
 (define (set-git-timeouts connection-timeout read-timeout)
   "Instruct Guile-Git to honor the given CONNECTION-TIMEOUT and READ-TIMEOUT
 when talking to remote Git servers.
-- 
2.49.0

Message #14 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Tomas Volf <~@wolfsden.cz>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 77875 <at> debbugs.gnu.org
Subject: Re: [PATCH 1/2] git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
Date: Mon, 21 Apr 2025 13:19:45 +0200

Hi,

few comments below.

Ludovic Courtès <ludo <at> gnu.org> writes:

> Fixes <https://issues.guix.gnu.org/66268>.
>
> Fixes a bug whereby ‘commit-relation’ and ‘commit-descendant?’ would
> provide an incorrect result when two distinct <commit> objects would
> exist for the same commit, which can happen when the commit’s metadata
> is beyond 4 KiB, as of libgit2 1.8/1.9.

Ooh, so this *used to work* in <1.8, interesting, I had no idea. :)

>
> This, in turn, would lead ‘guix pull’ & co. to wrongfully report an
> attempt to downgrade and pull to an unrelated commit.
>
> * guix/git.scm (commit-relation): When (guix graph) is available,
> rewrite in terms of ‘graph-descendant?’.
> (commit-descendant?): Likewise.
>
> Change-Id: Ie52b188a8dfa90c95a73387c3ab2fdd04d2bf3e9
> Reported-by: Tomas Volf <~@wolfsden.cz>
> ---
>  guix/git.scm | 83 ++++++++++++++++++++++++++++++++--------------------
>  1 file changed, 52 insertions(+), 31 deletions(-)
>
> diff --git a/guix/git.scm b/guix/git.scm
> index 01e0918588..cb26714d2d 100644
> --- a/guix/git.scm
> +++ b/guix/git.scm
> @@ -732,7 +732,7 @@ (define (print-git-error port key args default-printer)
>  ;;; Commit difference.
>  ;;;
>  
> -(define* (commit-closure commit #:optional (visited (setq)))
> +(define* (commit-closure commit #:optional (visited (setq))) ;to remove
>    "Return the closure of COMMIT as a set.  Skip commits contained in VISITED,
>  a set, and adjoin VISITED to the result."
>    (let loop ((commits (list commit))
> @@ -768,39 +768,60 @@ (define* (commit-difference new old #:optional (excluded '()))
>                   (cons head result)
>                   (set-insert head visited)))))))
>  
> -(define (commit-relation old new)
> -  "Return a symbol denoting the relation between OLD and NEW, two commit
> +(define commit-relation
> +  (if (resolve-module '(guix graph) #:ensure #f)  ;Guile-Git >= 0.10.0

Two notes here:

1. Should this not be '(git graph)?

2. I thought that when you do `guix pull`, the new Guix is built against
the packages in the newly pulled version.  So everyone who pulls these
changes, should also pull the guile-git 0.10.0 no?  It should not be
possible to end up in "new guix, old guile-git" situation.  So I do not
understand why you need both branches.

> +      (lambda (old new)
> +        "Return a symbol denoting the relation between OLD and NEW, two commit
>  objects: 'ancestor (meaning that OLD is an ancestor of NEW), 'descendant, or
>  'unrelated, or 'self (OLD and NEW are the same commit)."
> -  (if (eq? old new)
> -      'self
> -      (let ((newest (commit-closure new)))
> -        (if (set-contains? newest old)
> -            'ancestor
> -            (let* ((seen   (list->setq (commit-parents new)))
> -                   (oldest (commit-closure old seen)))
> -              (if (set-contains? oldest new)
> -                  'descendant
> -                  'unrelated))))))
> +        (let ((repository (commit-owner old))
> +              (old (commit-id old))
> +              (new (commit-id new)))
> +          (cond ((graph-descendant? repository new old)

How is the `graph-descendant?' set?  The `resolve-module' seems to check
for availability of the module, but it does not import bindings from it.
(At least that is what short experimentation in REPL suggests...)

> +                 'ancestor)
> +                ((oid=? old new)
> +                 'self)
> +                ((graph-descendant? repository old new)
> +                 'descendant)
> +                (else 'unrelated))))
> +      (lambda (old new)            ;remove when Guile-Git 0.10.0 is widespread
> +        (if (eq? old new)
> +            'self
> +            (let ((newest (commit-closure new)))
> +              (if (set-contains? newest old)
> +                  'ancestor
> +                  (let* ((seen   (list->setq (commit-parents new)))
> +                         (oldest (commit-closure old seen)))
> +                    (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)))))))))
> +(define commit-descendant?
> +  (if (resolve-module '(guix graph) #:ensure #f)  ;Guile-Git >= 0.10.0

Same question regarding '(git graph) here.

> +      (lambda (new old)
> +        "Return true if NEW is the descendant of one of OLD, a list of
> +commits."
> +        (let ((repository (commit-owner new))
> +              (new (commit-id new)))
> +          (any (lambda (old)
> +                 (let ((old (commit-id old)))
> +                   (or (graph-descendant? repository new old)
> +                       (oid=? old new))))
> +               old)))

I would be tempted to write this in terms of commit-relation and memq
with '(self descendant).  Beside being slightly easier to grasp (for
me), it would allow you to have just a single branch, since
commit-relation is available regardless of guile-git version.  Not sure
if there would be performance impact in <0.10.0 though.

> +      (lambda (new old)            ;remove when Guile-Git 0.10.0 is widespread
> +        (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)))))))))))
>  
>  
>  ;;

Have a nice day,
Tomas

-- 
There are only two hard things in Computer Science:
cache invalidation, naming things and off-by-one errors.

Message #17 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: 77875 <at> debbugs.gnu.org
Cc: Ludovic Courtès <ludo <at> gnu.org>
Subject: [PATCH v2 0/2] Use 'graph-descendant?' from Guile-Git instead of
 custom code
Date: Mon, 21 Apr 2025 23:26:24 +0200

Changes since v1:

  • Check for (git graph), not (guix graph), as noted by Tomas.

  • Improve wording in commit log.

Ludovic Courtès (2):
  git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
  git: Remove compatibility shim for Guile-Git <= 0.5.2.

 guix/git.scm | 90 ++++++++++++++++++++++++++++++----------------------
 1 file changed, 52 insertions(+), 38 deletions(-)


base-commit: ba53ff9cc403c7f0388e2dc932cb46e665e81be7
-- 
2.49.0

Message #20 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: 77875 <at> debbugs.gnu.org
Cc: Ludovic Courtès <ludo <at> gnu.org>
Subject: [PATCH v2 2/2] git: Remove compatibility shim for Guile-Git <= 0.5.2.
Date: Mon, 21 Apr 2025 23:26:26 +0200

Guile-Git 0.5.2 was released in July 2021.

* guix/git.scm (GITERR_HTTP): Remove.

Change-Id: I05b2ee36f786bd83ca91c8989912f83f6dde59c0
---
 guix/git.scm | 7 -------
 1 file changed, 7 deletions(-)

diff --git a/guix/git.scm b/guix/git.scm
index 1065479091..da0a668587 100644
--- a/guix/git.scm
+++ b/guix/git.scm
@@ -206,13 +206,6 @@ (define* (make-default-fetch-options #:key (verify-certificate? #t))
                                                  warn-for-invalid-certificate)))
     options))
 
-(define GITERR_HTTP
-  ;; Guile-Git <= 0.5.2 lacks this constant.
-  (let ((errors (resolve-interface '(git errors))))
-    (if (module-defined? errors 'GITERR_HTTP)
-        (module-ref errors 'GITERR_HTTP)
-        34)))
-
 (define (set-git-timeouts connection-timeout read-timeout)
   "Instruct Guile-Git to honor the given CONNECTION-TIMEOUT and READ-TIMEOUT
 when talking to remote Git servers.
-- 
2.49.0

Message #23 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: 77875 <at> debbugs.gnu.org
Cc: Ludovic Courtès <ludo <at> gnu.org>,
 Tomas Volf <~@wolfsden.cz>
Subject: [PATCH v2 1/2] git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
Date: Mon, 21 Apr 2025 23:26:25 +0200

Fixes <https://issues.guix.gnu.org/66268>.

Fixes a bug whereby ‘commit-relation’ and ‘commit-descendant?’ would
provide an incorrect result when two distinct <commit> objects would
exist for the same commit, which happens when the commit’s metadata is
beyond 4 KiB at least as of libgit2 1.8/1.9.

This, in turn, would lead ‘guix pull’ & co. to wrongfully report an
attempt to downgrade and pull to an unrelated commit.

* guix/git.scm (commit-relation): When (guix graph) is available,
rewrite in terms of ‘graph-descendant?’.
(commit-descendant?): Likewise.

Change-Id: Ie52b188a8dfa90c95a73387c3ab2fdd04d2bf3e9
Reported-by: Tomas Volf <~@wolfsden.cz>
---
 guix/git.scm | 83 ++++++++++++++++++++++++++++++++--------------------
 1 file changed, 52 insertions(+), 31 deletions(-)

diff --git a/guix/git.scm b/guix/git.scm
index 01e0918588..1065479091 100644
--- a/guix/git.scm
+++ b/guix/git.scm
@@ -732,7 +732,7 @@ (define (print-git-error port key args default-printer)
 ;;; Commit difference.
 ;;;
 
-(define* (commit-closure commit #:optional (visited (setq)))
+(define* (commit-closure commit #:optional (visited (setq))) ;to remove
   "Return the closure of COMMIT as a set.  Skip commits contained in VISITED,
 a set, and adjoin VISITED to the result."
   (let loop ((commits (list commit))
@@ -768,39 +768,60 @@ (define* (commit-difference new old #:optional (excluded '()))
                  (cons head result)
                  (set-insert head visited)))))))
 
-(define (commit-relation old new)
-  "Return a symbol denoting the relation between OLD and NEW, two commit
+(define commit-relation
+  (if (resolve-module '(git graph) #:ensure #f)   ;Guile-Git >= 0.10.0
+      (lambda (old new)
+        "Return a symbol denoting the relation between OLD and NEW, two commit
 objects: 'ancestor (meaning that OLD is an ancestor of NEW), 'descendant, or
 'unrelated, or 'self (OLD and NEW are the same commit)."
-  (if (eq? old new)
-      'self
-      (let ((newest (commit-closure new)))
-        (if (set-contains? newest old)
-            'ancestor
-            (let* ((seen   (list->setq (commit-parents new)))
-                   (oldest (commit-closure old seen)))
-              (if (set-contains? oldest new)
-                  'descendant
-                  'unrelated))))))
+        (let ((repository (commit-owner old))
+              (old (commit-id old))
+              (new (commit-id new)))
+          (cond ((graph-descendant? repository new old)
+                 'ancestor)
+                ((oid=? old new)
+                 'self)
+                ((graph-descendant? repository old new)
+                 'descendant)
+                (else 'unrelated))))
+      (lambda (old new)            ;remove when Guile-Git 0.10.0 is widespread
+        (if (eq? old new)
+            'self
+            (let ((newest (commit-closure new)))
+              (if (set-contains? newest old)
+                  'ancestor
+                  (let* ((seen   (list->setq (commit-parents new)))
+                         (oldest (commit-closure old seen)))
+                    (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)))))))))
+(define commit-descendant?
+  (if (resolve-module '(git graph) #:ensure #f)   ;Guile-Git >= 0.10.0
+      (lambda (new old)
+        "Return true if NEW is the descendant of one of OLD, a list of
+commits."
+        (let ((repository (commit-owner new))
+              (new (commit-id new)))
+          (any (lambda (old)
+                 (let ((old (commit-id old)))
+                   (or (graph-descendant? repository new old)
+                       (oid=? old new))))
+               old)))
+      (lambda (new old)            ;remove when Guile-Git 0.10.0 is widespread
+        (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)))))))))))
 
 
 ;;
-- 
2.49.0

Message #26 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: Tomas Volf <~@wolfsden.cz>
Cc: 77875 <at> debbugs.gnu.org
Subject: Re: [PATCH 1/2] git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
Date: Mon, 21 Apr 2025 23:26:56 +0200

Hi Tomas,

Tomas Volf <~@wolfsden.cz> writes:

> Ludovic Courtès <ludo <at> gnu.org> writes:
>
>> Fixes <https://issues.guix.gnu.org/66268>.
>>
>> Fixes a bug whereby ‘commit-relation’ and ‘commit-descendant?’ would
>> provide an incorrect result when two distinct <commit> objects would
>> exist for the same commit, which can happen when the commit’s metadata
>> is beyond 4 KiB, as of libgit2 1.8/1.9.
>
> Ooh, so this *used to work* in <1.8, interesting, I had no idea. :)

No no; what I meant is that this is known to be the case with 1.8 and
1.9, but I haven't checked with other versions.

>> +  (if (resolve-module '(guix graph) #:ensure #f)  ;Guile-Git >= 0.10.0
>
> Two notes here:
>
> 1. Should this not be '(git graph)?

Oops, yes!  Fixed locally.

> 2. I thought that when you do `guix pull`, the new Guix is built against
> the packages in the newly pulled version.  So everyone who pulls these
> changes, should also pull the guile-git 0.10.0 no?  It should not be
> possible to end up in "new guix, old guile-git" situation.  So I do not
> understand why you need both branches.

That's correct.  The second branch is a convenience for developers as I
wrote, typically for someone developing in “guix shell” but from a Guix
that doesn’t have 0.10.0 yet.  We can remove that second branch in a few
weeks.

> How is the `graph-descendant?' set?

It’s from the (git) module, automatically pulled in when available.

>> +      (lambda (new old)
>> +        "Return true if NEW is the descendant of one of OLD, a list of
>> +commits."
>> +        (let ((repository (commit-owner new))
>> +              (new (commit-id new)))
>> +          (any (lambda (old)
>> +                 (let ((old (commit-id old)))
>> +                   (or (graph-descendant? repository new old)
>> +                       (oid=? old new))))
>> +               old)))
>
> I would be tempted to write this in terms of commit-relation and memq
> with '(self descendant).  Beside being slightly easier to grasp (for
> me), it would allow you to have just a single branch, since
> commit-relation is available regardless of guile-git version.  Not sure
> if there would be performance impact in <0.10.0 though.

I thought about this but I think the implementation above is slightly
more efficient, and since the "else" branch will be removed soon, let's
not bother.

Sending v2 right away.

Thanks,
Ludo'.

Message #29 received at 77875 <at> debbugs.gnu.org (full text, mbox):

From: Tomas Volf <~@wolfsden.cz>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 77875 <at> debbugs.gnu.org
Subject: Re: [PATCH v2 1/2] git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
Date: Tue, 22 Apr 2025 18:51:54 +0200

Ludovic Courtès <ludo <at> gnu.org> writes:

> Fixes <https://issues.guix.gnu.org/66268>.
>
> Fixes a bug whereby ‘commit-relation’ and ‘commit-descendant?’ would
> provide an incorrect result when two distinct <commit> objects would
> exist for the same commit, which happens when the commit’s metadata is
> beyond 4 KiB at least as of libgit2 1.8/1.9.
>
> This, in turn, would lead ‘guix pull’ & co. to wrongfully report an
> attempt to downgrade and pull to an unrelated commit.
>
> * guix/git.scm (commit-relation): When (guix graph) is available,

You forgot to switch to (git graph) here.

> rewrite in terms of ‘graph-descendant?’.
> (commit-descendant?): Likewise.
>
> Change-Id: Ie52b188a8dfa90c95a73387c3ab2fdd04d2bf3e9
> Reported-by: Tomas Volf <~@wolfsden.cz>
> ---
>  guix/git.scm | 83 ++++++++++++++++++++++++++++++++--------------------
>  1 file changed, 52 insertions(+), 31 deletions(-)
>
> diff --git a/guix/git.scm b/guix/git.scm
> index 01e0918588..1065479091 100644
> --- a/guix/git.scm
> +++ b/guix/git.scm
> @@ -732,7 +732,7 @@ (define (print-git-error port key args default-printer)
>  ;;; Commit difference.
>  ;;;
>  
> -(define* (commit-closure commit #:optional (visited (setq)))
> +(define* (commit-closure commit #:optional (visited (setq))) ;to remove
>    "Return the closure of COMMIT as a set.  Skip commits contained in VISITED,
>  a set, and adjoin VISITED to the result."
>    (let loop ((commits (list commit))
> @@ -768,39 +768,60 @@ (define* (commit-difference new old #:optional (excluded '()))
>                   (cons head result)
>                   (set-insert head visited)))))))
>  
> -(define (commit-relation old new)
> -  "Return a symbol denoting the relation between OLD and NEW, two commit
> +(define commit-relation
> +  (if (resolve-module '(git graph) #:ensure #f)   ;Guile-Git >= 0.10.0
> +      (lambda (old new)
> +        "Return a symbol denoting the relation between OLD and NEW, two commit
>  objects: 'ancestor (meaning that OLD is an ancestor of NEW), 'descendant, or
>  'unrelated, or 'self (OLD and NEW are the same commit)."
> -  (if (eq? old new)
> -      'self
> -      (let ((newest (commit-closure new)))
> -        (if (set-contains? newest old)
> -            'ancestor
> -            (let* ((seen   (list->setq (commit-parents new)))
> -                   (oldest (commit-closure old seen)))
> -              (if (set-contains? oldest new)
> -                  'descendant
> -                  'unrelated))))))
> +        (let ((repository (commit-owner old))
> +              (old (commit-id old))
> +              (new (commit-id new)))
> +          (cond ((graph-descendant? repository new old)
> +                 'ancestor)
> +                ((oid=? old new)
> +                 'self)
> +                ((graph-descendant? repository old new)
> +                 'descendant)
> +                (else 'unrelated))))
> +      (lambda (old new)            ;remove when Guile-Git 0.10.0 is widespread
> +        (if (eq? old new)
> +            'self
> +            (let ((newest (commit-closure new)))
> +              (if (set-contains? newest old)
> +                  'ancestor
> +                  (let* ((seen   (list->setq (commit-parents new)))
> +                         (oldest (commit-closure old seen)))
> +                    (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)))))))))
> +(define commit-descendant?
> +  (if (resolve-module '(git graph) #:ensure #f)   ;Guile-Git >= 0.10.0
> +      (lambda (new old)
> +        "Return true if NEW is the descendant of one of OLD, a list of
> +commits."
> +        (let ((repository (commit-owner new))
> +              (new (commit-id new)))
> +          (any (lambda (old)
> +                 (let ((old (commit-id old)))
> +                   (or (graph-descendant? repository new old)
> +                       (oid=? old new))))
> +               old)))
> +      (lambda (new old)            ;remove when Guile-Git 0.10.0 is widespread
> +        (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)))))))))))
>  
>  
>  ;;

Other then the commit message looks good.

Reviewed-by: Tomas Volf <~@wolfsden.cz>

-- 
There are only two hard things in Computer Science:
cache invalidation, naming things and off-by-one errors.

Message #34 received at 77875-done <at> debbugs.gnu.org (full text, mbox):

From: Ludovic Courtès <ludo <at> gnu.org>
To: Tomas Volf <~@wolfsden.cz>
Cc: 77875-done <at> debbugs.gnu.org
Subject: Re: [PATCH v2 1/2] git: Use ‘graph-descendant?’ from Guile-Git >= 0.10.0 when available.
Date: Wed, 23 Apr 2025 12:30:56 +0200

Tomas Volf <~@wolfsden.cz> writes:

> Ludovic Courtès <ludo <at> gnu.org> writes:
>
>> Fixes <https://issues.guix.gnu.org/66268>.
>>
>> Fixes a bug whereby ‘commit-relation’ and ‘commit-descendant?’ would
>> provide an incorrect result when two distinct <commit> objects would
>> exist for the same commit, which happens when the commit’s metadata is
>> beyond 4 KiB at least as of libgit2 1.8/1.9.
>>
>> This, in turn, would lead ‘guix pull’ & co. to wrongfully report an
>> attempt to downgrade and pull to an unrelated commit.
>>
>> * guix/git.scm (commit-relation): When (guix graph) is available,
>
> You forgot to switch to (git graph) here.

Oops.  Fixed and pushed as ee6d2a77a3f07c4b81fd31bc7aa5d07accc317bd.

Thanks,
Ludo’.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.