bug#18247: Cyclic dependencies in (gnu package *) modules

bug#18247: Cyclic dependencies in (gnu package *) modules

[mhw]

I'm currently unable to compile guix from git, with error messages that
suggest cyclic dependencies between the modules.  I just computed the
strongly connected components of the (gnu package *) modules.  The
non-trivial ones are listed below.

There are three cycles of size 2:

((gnu packages emacs)  (gnu packages version-control))
((gnu packages flex)   (gnu packages bison))
((gnu packages python) (gnu packages zip))

And one large strongly-connected component containing 51 modules:

((gnu packages acl)
 (gnu packages gettext)
 (gnu packages xml)
 (gnu packages linux)
 (gnu packages gtk)
 (gnu packages xorg)
 (gnu packages gnupg)
 (gnu packages glib)
 (gnu packages base)
 (gnu packages texinfo)
 (gnu packages gcc)
 (gnu packages openldap)
 (gnu packages groff)
 (gnu packages netpbm)
 (gnu packages ghostscript)
 (gnu packages tcl)
 (gnu packages fontutils)
 (gnu packages cyrus-sasl)
 (gnu packages mit-krb5)
 (gnu packages curl)
 (gnu packages ssh)
 (gnu packages gsasl)
 (gnu packages shishi)
 (gnu packages gnutls)
 (gnu packages gl)
 (gnu packages pdf)
 (gnu packages lesstif)
 (gnu packages gnome)
 (gnu packages libcanberra)
 (gnu packages xiph)
 (gnu packages pulseaudio)
 (gnu packages web)
 (gnu packages docbook)
 (gnu packages avahi)
 (gnu packages algebra)
 (gnu packages mpi)
 (gnu packages valgrind)
 (gnu packages gdb)
 (gnu packages dejagnu)
 (gnu packages doxygen)
 (gnu packages graphviz)
 (gnu packages gd)
 (gnu packages gstreamer)
 (gnu packages iso-codes)
 (gnu packages rrdtool)
 (gnu packages maths)
 (gnu packages texlive)
 (gnu packages tcsh)
 (gnu packages lisp)
 (gnu packages fltk)
 (gnu packages attr))

     Mark

bug#18247: Cyclic dependencies in (gnu package *) modules

[mhw]

[-- Attachment #1: Type: text/plain, Size: 170 bytes --]

I hacked up the following Guile script to automatically find cyclic
dependencies in (gnu packages *).  It must be run from Guix's top-level
source directory.

     Mark


[-- Attachment #2: Script to find cyclic dependencies in guix package modules --]
[-- Type: text/plain, Size: 5261 bytes --]

(use-modules (srfi srfi-1)
             (srfi srfi-26)
             (ice-9 match)
             (ice-9 ftw)
             (ice-9 pretty-print))

;;;
;;; Tarjan's strongly connected components algorithm
;;;
;;; Robert Tarjan, Depth-first search and linear graph algorithms.
;;; SIAM Journal on Computing, 1(2):146-160, 1972.
;;;
;;;
;;; vertices is the list of vertices, which may be any objects that
;;; can be distinguished using 'equal?'.
;;;
;;; edges is the list of edges, where each edge is a pair (w . v)
;;; representing the directed edge w => v, for vertices w and v.
;;;
;;; The return value is a list of the strongly-connected components,
;;; where each strongly-connected component (SCC) is represented as a
;;; list of the vertices it contains.  The returned SCCs are sorted in
;;; topological order.
;;;
(define (strongly-connected-components vertices edges)
  (define size (length vertices))
  (define vs (iota size))

  (define lookup
    (let ((t (make-hash-table size)))
      (for-each (cut hash-set! t <> <>) vertices vs)
      (cut hash-ref t <>)))

  (define name
    (let ((t (make-vector size #f)))
      (for-each (cut vector-set! t <> <>) vs vertices)
      (cut vector-ref t <>)))

  (define (vector-update! v i f)
    (vector-set! v i (f (vector-ref v i))))

  (define (compose f g) (lambda (x) (f (g x))))

  (define successors
    (let ((t (make-vector size '())))
      (for-each (lambda (v w) (vector-update! t v (cut cons w <>)))
                (map (compose lookup car) edges)
                (map (compose lookup cdr) edges))
      (cut vector-ref t <>)))

  (define new-index
    (let ((i -1))
      (lambda ()
        (set! i (+ i 1))
        i)))

  (define index-table (make-vector size #f))
  (define index       (cut vector-ref  index-table <>))
  (define set-index!  (cut vector-set! index-table <> <>))

  (define lowlink-table (make-vector size size))
  (define lowlink (cut vector-ref lowlink-table <>))
  (define (update-lowlink! v x)
    (if v (vector-update! lowlink-table v (cut min x <>))))

  (define done-table (make-bitvector size #f))
  (define done? (cut bitvector-ref  done-table <>))
  (define done! (cut bitvector-set! done-table <> #t))

  (define results '())
  (define pending '())

  (define (finalize! v)
    (let loop ((names '()) (p pending))
      (done! (car p))
      (cond ((eqv? v (car p))
             (set! pending (cdr p))
             (set! results (cons (cons (name v) names)
                                 results)))
            (else (loop (cons (name (car p))
                              names)
                        (cdr p))))))

  (let loop ((v #f) (ws vs) (stack '()))
    (cond ((pair? ws)
           (let ((w (car ws)))
             (cond ((index w) => (lambda (wi)
                                   (if (not (done? w))
                                       (update-lowlink! v wi))
                                   (loop v (cdr ws) stack)))
                   (else (let ((wi (new-index)))
                           (set-index! w wi)
                           (update-lowlink! w wi)
                           (set! pending (cons w pending))
                           (loop w (successors w)
                                 (cons (cons v (cdr ws))
                                       stack)))))))
          ((pair? stack)
           (if (and v (= (index v) (lowlink v)))
               (finalize! v))
           (update-lowlink! (caar stack) (lowlink v))
           (loop (caar stack) (cdar stack) (cdr stack)))
          (else results))))

(chdir "gnu/packages")

(define files (scandir "." (cut string-suffix? ".scm" <>)))
(define headers (map (cut call-with-input-file <> read)
                     files))
(define modules
  (filter-map
   (lambda (header)
     (match header
       (('define-module ('gnu 'packages name0 name* ...) . _)
        `(gnu packages ,name0 ,@name*))
       (('define-module module-name . _)
        (format (current-warning-port)
                "Warning: found unexpected module name ~S in gnu/packages/*.scm~%"
                module-name)
        #f)))
   headers))

(define dependencies
  (append-map
   (lambda (header)
     (match header
       (('define-module module . rest)
        (let loop ((rest rest)
                   (deps '()))
          (match rest
            (() deps)
            ((#:use-module ('gnu 'packages name0 name* ...) . rest)
             (loop rest `((,module . (gnu packages ,name0 ,@name*)) . ,deps)))
            ((#:use-module (('gnu 'packagess name0 name* ...) . _) . rest)
             (loop rest `((,module . (gnu packages ,name0 ,@name*)) . ,deps)))
            ((#:use-module _ . rest)
             (loop rest deps))
            ((#:export _ . rest)
             (loop rest deps))
            ((#:autoload _ _ . rest)
             (loop rest deps)))))))
   headers))

(define sccs (strongly-connected-components modules dependencies))

(define (non-trivial? scc)
  (not (= 1 (length scc))))

(define non-trivial-sccs (filter non-trivial? sccs))

(unless (zero? (length non-trivial-sccs))
  (display "Found the following non-trivial strongly-connected components:")
  (newline)
  (for-each (lambda (scc)
              (pretty-print scc)
              (newline))
            non-trivial-sccs))

bug#18247: Cyclic dependencies in (gnu package *) modules

[Ludovic Courtès]

mhw@netris.org skribis:

> I'm currently unable to compile guix from git, with error messages that
> suggest cyclic dependencies between the modules.

Indeed.  That is fixed by reverting c5d8376.  Can you confirm?

> I just computed the strongly connected components of the (gnu package
> *) modules.  The non-trivial ones are listed below.
>
> There are three cycles of size 2:
>
> ((gnu packages emacs)  (gnu packages version-control))
> ((gnu packages flex)   (gnu packages bison))
> ((gnu packages python) (gnu packages zip))
>
> And one large strongly-connected component containing 51 modules:

Ouch.

Well, that is not really a problem per se.  The real problem is when
top-level bindings refer to each other, of course.

But anyway, I agree we need tooling or something to help deal with this
kind of issues.  Perhaps something like the script you posted, but that
would look at the set of bindings referenced from the top-level of a
module?  Or can we do better?

If Guile supported phases, such circular references would not be a
problem since it would not have to evaluate all of the imported modules
at expansion phase, just the ‘define-module’ clause.

Thanks,
Ludo’.

bug#18247: Cyclic dependencies in (gnu package *) modules

[Mark H Weaver]

ludo@gnu.org (Ludovic Courtès) writes:

> mhw@netris.org skribis:
>
>> I'm currently unable to compile guix from git, with error messages that
>> suggest cyclic dependencies between the modules.
>
> Indeed.  That is fixed by reverting c5d8376.  Can you confirm?

Yes, that solves the problem for me.

>> I just computed the strongly connected components of the (gnu package
>> *) modules.  The non-trivial ones are listed below.
>>
>> There are three cycles of size 2:
>>
>> ((gnu packages emacs)  (gnu packages version-control))
>> ((gnu packages flex)   (gnu packages bison))
>> ((gnu packages python) (gnu packages zip))
>>
>> And one large strongly-connected component containing 51 modules:
>
> Ouch.
>
> Well, that is not really a problem per se.  The real problem is when
> top-level bindings refer to each other, of course.

To be more precise, the relevant question is: which bindings from other
modules are needed when a module is _loaded_.  In other words, we need
to worry about cycles in a graph, but a different graph than the one my
script computed.

I think the graph we need to consider is one that contains one vertex
per module, and an directed edge from module A to B if and only if
loading module A requires looking up a binding from module B.

Does that sound right to you?

Unfortunately, it seems to me that the most common kinds of cross-module
references between (gnu packages *) modules are references in 'inputs'
or 'native-inputs' fields, and those need to be looked up at module load
time, right?

> But anyway, I agree we need tooling or something to help deal with this
> kind of issues.  Perhaps something like the script you posted, but that
> would look at the set of bindings referenced from the top-level of a
> module?  Or can we do better?
>
> If Guile supported phases, such circular references would not be a
> problem since it would not have to evaluate all of the imported modules
> at expansion phase, just the ‘define-module’ clause.

I'd very much like to add phases to Guile's macro expander at some
point, but it would have to be done between major releases.  It would
likely break a lot of existing code.

    Thanks,
      Mark

bug#18247: Cyclic dependencies in (gnu package *) modules

[mhw]

I wrote:
> Unfortunately, it seems to me that the most common kinds of cross-module
> references between (gnu packages *) modules are references in 'inputs'
> or 'native-inputs' fields, and those need to be looked up at module load
> time, right?

I see now that 'inputs' and 'native-inputs' are "thunked" fields, so the
bindings don't have to be looked up until those fields are accessed at
run time.

     Mark

bug#18247: Cyclic dependencies in (gnu package *) modules

[mhw]

I now understand the problem more clearly.

The problem arises when a package in module A inherits from a package in
module B, if there is a cycle in the use-module graph involving A and B.

In this case, (gnu packages base) contains packages that inherit gcc-4.8
from (gnu packages gcc).

Commit c5d837684359e3629c4ac96297a25d1165edcb39 creates cycles between
those two modules.  This fact is not immediately obvious because it only
adds an edge from (gnu packages texinfo) -> (gnu packages gettext).
Here's one such cycle, with ==> being the newly added edge:

  gcc -> texinfo ==> gettext -> xml -> gnome -> glib -> base -> gcc

When there exists a cycle involving two modules, the order in which they
are loaded cannot be assured, because of the way module loading is done
in Guile.

In the short term, it might help to move (gnu packages gcc) into
(gnu packages base), and more generally to avoid inheriting from
imported packages, at least among modules that are likely to be
involved in cycles, such as core modules.

       Mark

bug#18247: Cyclic dependencies in (gnu package *) modules

[Ludovic Courtès]

As a stop-gap measure, I’ve worked around the problem in commit d759cf6,
which removes the dependency from texinfo to gettext.

(Éric: I see one test failure in texi2html, which is a priori unrelated
to the change.  Could you check what’s going on?)

mhw@netris.org skribis:

> In the short term, it might help to move (gnu packages gcc) into
> (gnu packages base), and more generally to avoid inheriting from
> imported packages, at least among modules that are likely to be
> involved in cycles, such as core modules.

Merging modules is not really satisfactory either.  :-/

Perhaps one possibility would be to reorganize base.scm so that
%final-inputs and things it depends on are thunked.

Another possibility, probably better, would be to split base into two
modules: one that exports the normal package definitions (the first page
of base.scm, in terms of C-x n p), and one that exports %final-inputs
and related stuff (the second page).  Normally the latter will not have
to be used directly, except by (guix build-system gnu) and related
stuff.

WDYT?

Thanks,
Ludo’.

bug#18247: Cyclic dependencies in (gnu package *) modules

[Eric Bavier]

Ludovic Courtès writes:

> As a stop-gap measure, I’ve worked around the problem in commit d759cf6,
> which removes the dependency from texinfo to gettext.
>
> (Éric: I see one test failure in texi2html, which is a priori unrelated
> to the change.  Could you check what’s going on?)

The problem is that texi2html does actually require gettext.  Its
makefile wants to install mo files that are not present in the
distribution (so msgfmt is required).  Configuring with --disable-nls
causes the resulting script to fail at runtime.

Perhaps moving texi2html into its own module would solve the circular
dependency?

-- 
Eric Bavier

bug#18247: Cyclic dependencies in (gnu package *) modules

[Mark H Weaver]

Eric Bavier <ericbavier@gmail.com> writes:

> Ludovic Courtès writes:
>
>> As a stop-gap measure, I’ve worked around the problem in commit d759cf6,
>> which removes the dependency from texinfo to gettext.
>>
>> (Éric: I see one test failure in texi2html, which is a priori unrelated
>> to the change.  Could you check what’s going on?)
>
> The problem is that texi2html does actually require gettext.  Its
> makefile wants to install mo files that are not present in the
> distribution (so msgfmt is required).  Configuring with --disable-nls
> causes the resulting script to fail at runtime.
>
> Perhaps moving texi2html into its own module would solve the circular
> dependency?

That would be one way to avoid the circular dependency, yes.

      Mark

bug#18247: Cyclic dependencies in (gnu package *) modules

[Ludovic Courtès]

Eric Bavier <ericbavier@gmail.com> skribis:

> Ludovic Courtès writes:
>
>> As a stop-gap measure, I’ve worked around the problem in commit d759cf6,
>> which removes the dependency from texinfo to gettext.
>>
>> (Éric: I see one test failure in texi2html, which is a priori unrelated
>> to the change.  Could you check what’s going on?)
>
> The problem is that texi2html does actually require gettext.

No, it really only needed it because texi2html.pl was modified by the
patch, which triggered a rule to re-compute PO files.

I just tried with current master with #:tests? #f, and it does pass.
Perhaps that’s an intermittent test failure?  Can you reproduce it?

Thanks,
Ludo’.

bug#18247: Cyclic dependencies in (gnu package *) modules

[Eric Bavier]

[-- Attachment #1: Type: text/plain, Size: 1209 bytes --]


Ludovic Courtès writes:

> Eric Bavier <ericbavier@gmail.com> skribis:
>
>> Ludovic Courtès writes:
>>
>>> As a stop-gap measure, I’ve worked around the problem in commit d759cf6,
>>> which removes the dependency from texinfo to gettext.
>>>
>>> (Éric: I see one test failure in texi2html, which is a priori unrelated
>>> to the change.  Could you check what’s going on?)
>>
>> The problem is that texi2html does actually require gettext.
>
> No, it really only needed it because texi2html.pl was modified by the
> patch, which triggered a rule to re-compute PO files.

After reseting the timestamp, the makefile still wants to run msgexec
for some reason. This doesn't appear to be fatal...

> I just tried with current master with #:tests? #f, and it does pass.

Yes, with #:tests? #f it builds succesfully; I did not try that.  It
appears the resulting texi2html tool is even functional::

  $ /gnu/store/...-texi2html/bin/texi2html doc/guix.texi
  $ echo $?
  0a

> Perhaps that’s an intermittent test failure?  Can you reproduce it?

The test failures are reproducible on my end.  The attached patch allows
the tests to run successfully.  Let me know if this seems like a
reasonable solution.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-gnu-texi2html-Fix-tests-in-the-absense-of-gettext.patch --]
[-- Type: text/x-diff, Size: 4258 bytes --]

From e0f0ff27fce4e5b62105ffd28281a78552c1dc39 Mon Sep 17 00:00:00 2001
From: Eric Bavier <bavier@member.fsf.org>
Date: Sat, 16 Aug 2014 00:56:42 -0500
Subject: [PATCH] gnu: texi2html: Fix tests in the absense of gettext.

* gnu/packages/patches/texi2html-i18n.patch: New patch.
* gnu/packages/texinfo.scm (texi2html)[source]: Use it.
* gnu-system.am (dist_patch_DATA): Add it.
---
 gnu-system.am                             |    1 +
 gnu/packages/patches/texi2html-i18n.patch |   50 +++++++++++++++++++++++++++++
 gnu/packages/texinfo.scm                  |    3 +-
 3 files changed, 53 insertions(+), 1 deletion(-)
 create mode 100644 gnu/packages/patches/texi2html-i18n.patch

diff --git a/gnu-system.am b/gnu-system.am
index 66a1677..f29f3f6 100644
--- a/gnu-system.am
+++ b/gnu-system.am
@@ -378,6 +378,7 @@ dist_patch_DATA =						\
   gnu/packages/patches/tcsh-fix-autotest.patch			\
   gnu/packages/patches/teckit-cstdio.patch			\
   gnu/packages/patches/texi2html-document-encoding.patch	\
+  gnu/packages/patches/texi2html-i18n.patch			\
   gnu/packages/patches/udev-gir-libtool.patch			\
   gnu/packages/patches/util-linux-perl.patch			\
   gnu/packages/patches/valgrind-glibc.patch			\
diff --git a/gnu/packages/patches/texi2html-i18n.patch b/gnu/packages/patches/texi2html-i18n.patch
new file mode 100644
index 0000000..eba903d
--- /dev/null
+++ b/gnu/packages/patches/texi2html-i18n.patch
@@ -0,0 +1,50 @@
+Do not try to regenerate po files; use the reference files that are packaged
+in the tarball.
+
+--- a/Makefile.in	2010-06-30 17:02:28.000000000 -0500
++++ b/Makefile.in	2014-08-16 00:22:38.447050269 -0500
+@@ -1022,15 +1022,7 @@
+ 
+ i18n/en.thl i18n/: $(po_document_dir)/po_document/$(PACKAGE)_document.pot
+ 	$(MKDIR_P) i18n
+-	if test '$(USE_NLS)' = 'yes'; then \
+-	  for file in "$(srcdir)/$(po_document_dir)/po_document/"*".po"; do lang=`basename "$$file" .po | sed 's/\..*//'`; \
+-		test "$$lang" = 'en' && continue; \
+-		msgexec -i "$$file" "$(srcdir)/gettext_to_separated.pl" | "$(srcdir)/separated_to_hash.pl" $$lang > i18n/$$lang.thl; \
+-	  done; \
+-	  msgexec -i $< "$(srcdir)/gettext_to_separated.pl" | "$(srcdir)/separated_to_hash.pl" en > i18n/en.thl; \
+-	else \
+-	  cp -p i18n_ref/*.thl i18n; \
+-	fi
++	cp -p i18n_ref/*.thl i18n
+ 
+ i18n_ref:
+ 	$(MKDIR_P) i18n_ref
+
+Have install-sh install .mo files locally for in-source tests, so that msgfmt
+is not needed.
+
+--- a/Makefile.in	2010-06-30 17:02:28.000000000 -0500
++++ b/Makefile.in	2014-08-16 00:22:38.447050269 -0500
+@@ -1052,19 +1044,8 @@
+ # update the po files, and install locally the .mo files for the in
+ # source tests
+ check-local: makeinfo.pl texi2any.pl
+-	if test '$(USE_NLS)' = 'yes'; then \
+-	  cd $(po_document_dir)/po_document && $(MAKE) $(AM_MAKEFLAGS) update-po; \
+-	fi
+-	rm -rf locales
+-	for file in "$(srcdir)/$(po_document_dir)/po_document/"*.po; do \
+-	  basename=`basename "$$file" .po` ; \
+-	  $(MKDIR_P) "locales/$$basename/LC_MESSAGES/" ; \
+-	  if test '$(USE_NLS)' = 'yes'; then \
+-	    $(MSGFMT) "$$file" -o "locales/$$basename/LC_MESSAGES/texi2html_document.mo" ; \
+-	  else \
+-	    cp -p "$(srcdir)/$(po_document_dir)/po_document/$$basename.mo" "locales/$$basename/LC_MESSAGES/texi2html_document.mo" ; \
+-	  fi; \
+-	done
++	$(MAKE) -C po_document localedir="$(abs_srcdir)/locales" install-data
++	$(MAKE) -C po_messages localedir="$(abs_srcdir)/locales" install-data
+ 
+ makeinfo.pl texi2any.pl:
+ 	-$(LN_S) $(srcdir)/texi2html.pl $@
diff --git a/gnu/packages/texinfo.scm b/gnu/packages/texinfo.scm
index c199fd6..0cce38b 100644
--- a/gnu/packages/texinfo.scm
+++ b/gnu/packages/texinfo.scm
@@ -79,7 +79,8 @@ is on expressing the content semantically, avoiding physical markup commands.")
                (base32
                 "1yprv64vrlcbksqv25asplnjg07mbq38lfclp1m5lj8cw878pag8"))
               (patches
-               (list (search-patch "texi2html-document-encoding.patch")))
+               (list (search-patch "texi2html-document-encoding.patch")
+                     (search-patch "texi2html-i18n.patch")))
               (snippet
                ;; This file is modified by the patch above, but reset its
                ;; timestamp so we don't trigger the rule to update PO files,
-- 
1.7.9.5


[-- Attachment #3: Type: text/plain, Size: 17 bytes --]


-- 
Eric Bavier

bug#18247: Cyclic dependencies in (gnu package *) modules

[Ludovic Courtès]

Eric Bavier <ericbavier@gmail.com> skribis:

> From e0f0ff27fce4e5b62105ffd28281a78552c1dc39 Mon Sep 17 00:00:00 2001
> From: Eric Bavier <bavier@member.fsf.org>
> Date: Sat, 16 Aug 2014 00:56:42 -0500
> Subject: [PATCH] gnu: texi2html: Fix tests in the absense of gettext.
>
> * gnu/packages/patches/texi2html-i18n.patch: New patch.
> * gnu/packages/texinfo.scm (texi2html)[source]: Use it.
> * gnu-system.am (dist_patch_DATA): Add it.

Oh so ‘check-local’ would trigg a makefile rule to build PO files.

Then the patch looks good to me, OK to commit.

Thanks!

Ludo’.

bug#18247: Cyclic dependencies in (gnu package *) modules

[Ludovic Courtès]

ludo@gnu.org (Ludovic Courtès) skribis:

> Another possibility, probably better, would be to split base into two
> modules: one that exports the normal package definitions (the first page
> of base.scm, in terms of C-x n p), and one that exports %final-inputs
> and related stuff (the second page).  Normally the latter will not have
> to be used directly, except by (guix build-system gnu) and related
> stuff.

Commit bdb3695 does that.

It helps a bit already, in that, for instance, adding Guile-Charting and
its dependency on (gnu packages gtk) would have been impossible before,
but here does not cause any problems.

Comments welcome!

I’m closing this bug but we’ll certainly have to keep an eye on it, so
feel free to reopen as you see fit.

Thanks,
Ludo’.

bug#18247: Cyclic dependencies in (gnu package *) modules

[Ludovic Courtès]

Mark H Weaver <mhw@netris.org> skribis:

> I think the graph we need to consider is one that contains one vertex
> per module, and an directed edge from module A to B if and only if
> loading module A requires looking up a binding from module B.
>
> Does that sound right to you?

Yes, exactly.

Ludo’.