Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Mark H Weaver]

Hi,

I just got bitten again by a problem that has plagued us over the years,
namely our extensive tangled knot of cyclic module dependencies which
occasionally causes hard-to-debug compilation failures.

Here's how it looked this time, while running 'make' in my git checkout:

--8<---------------cut here---------------start------------->8---
Backtrace:
In ice-9/boot-9.scm:
  2879:24 19 (_)
   230:29 18 (map1 _)
   230:29 17 (map1 _)
   230:29 16 (map1 _)
   230:29 15 (map1 _)
   230:29 14 (map1 _)
   230:29 13 (map1 _)
   230:29 12 (map1 _)
   230:17 11 (map1 (((gnu packages linux)) ((gnu packages ncurses))))
  2792:17 10 (resolve-interface (gnu packages linux) #:select _ #:hide _ #:prefix _ #:renamer _ #:version _)
  2718:10  9 (_ (gnu packages linux) _ _ #:ensure _)
  2986:16  8 (try-module-autoload _ _)
   2316:4  7 (save-module-excursion _)
  3006:22  6 (_)
In unknown file:
           5 (primitive-load-path "gnu/packages/linux" #<procedure 13b8740 at ice-9/boot-9.scm:2993:32 ()>)
In ice-9/eval.scm:
    619:8  4 (_ #f)
   626:19  3 (_ #<directory (gnu packages linux) 13df820>)
   191:35  2 (_ #(#<directory (gnu packages linux) 13df820> #<variable 4b8c1e0 value: #<procedure loop (a)>>))
   223:20  1 (proc #(#<directory (gnu packages linux) 13df820> #<variable 4b8c1e0 value: #<procedure loop (a)>>))
In unknown file:
           0 (%resolve-variable (7 . ncurses) #<directory (gnu packages linux) 13df820>)

ERROR: In procedure %resolve-variable:
ERROR: Unbound variable: ncurses
make[2]: *** [Makefile:5222: make-go] Error 1
make[2]: Leaving directory '/home/mhw/guix'
make[1]: *** [Makefile:4353: all-recursive] Error 1
make[1]: Leaving directory '/home/mhw/guix'
make: *** [Makefile:2943: all] Error 2
--8<---------------cut here---------------end--------------->8---

It was caused by the following commit, made 2.5 weeks ago, although it
didn't cause trouble for me until today:

dannym@scratchpost.org (Danny Milosavljevic) writes:

> dannym pushed a commit to branch master
> in repository guix.
>
> commit 87ffa416af029722a73b3244b409f86e39086bc3
> Author: Danny Milosavljevic <dannym@scratchpost.org>
> Date:   Wed Jul 5 22:31:03 2017 +0200
>
>     gnu: Add ncurses-with-gpm.
>     
>     * gnu/packages/linux.scm (ncurses/gpm): New variable.
> ---
>  gnu/packages/linux.scm | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
>
> diff --git a/gnu/packages/linux.scm b/gnu/packages/linux.scm
> index 1a9e9d7..58f6f36 100644
> --- a/gnu/packages/linux.scm
> +++ b/gnu/packages/linux.scm
> @@ -3013,6 +3013,18 @@ applications running on the Linux console.  It allows users to select items
>  and copy/paste text in the console and in xterm.")
>      (license license:gpl2+)))
>  
> +(define-public ncurses/gpm
> +  (package/inherit ncurses
> +    (name "ncurses-with-gpm")
> +    (arguments
> +        (substitute-keyword-arguments (package-arguments ncurses)
> +         ((#:configure-flags cf)
> +          `(cons (string-append "--with-gpm="
> +                                (assoc-ref %build-inputs "gpm")
> +                                "/lib/libgpm.so.2") ,cf))))
> +    (inputs
> +     `(("gpm" ,gpm)))))

I don't blame Danny for this, because it is a non-obvious mistake that
any of us could make, invited by our IMO questionable practice of
allowing cyclic module dependencies, and not sufficiently mitigated by
warnings about this issue.

So, it seems that the time has come again to review the rules that we
must follow in order to avoid problems from cyclic module dependencies:

If two modules are involved in a cyclic dependency, i.e. if they are
part of a cycle in the module-import graph, then neither of them can
safely use macros defined in the other one, and any variable references
from one to the other must be *delayed* until after the modules are
loaded.

Briefly, for our purposes, if a variable reference occurs within the
'arguments', 'inputs', 'propagated-inputs', 'native-inputs', or
'replacement' fields of a package, then it is delayed.  A variable
reference is also delayed if it is made within a procedure body, and if
that procedure is not called during module loading.

However, when a package inherits from another package, then the variable
reference to the inherited package is *not* delayed.  In such a case,
the variable must be accessed while the module is being loaded.

That's what happened here.  The above commit introduced a package
'ncurses/gpm' defined in (gnu packages linux) that inherited from
'ncurses' defined in (gnu packages ncurses).  Those two modules are part
of the same cycle in the module-import graph, so it effectively created
a land mine waiting for some unfortunate person to step on.

I should explain in more detail why this happens.

Normally, if module B imports module A, then we arrange to load module A
before loading module B.  This ensures that module B can use all of the
facilities of module A at any time without restrictions.

However, if module A and module B import each other (directly or
indirectly) then obviously we cannot load each one before loading the
other.  Modern Scheme standards simply prohibit cyclic module
dependencies.

Guile is more lax about this, and here's what happens: if module A and
module B import each other, then one of them will be loaded before the
other one, and it's not obvious which will come first[*].  In practice,
we must ensure that things work regardless of the order.

In this case, things worked as long as (gnu package ncurses) was loaded
first, but if (gnu packages linux) was loaded first, then it failed.

Commit c67d80563fc7021484602889454de534469f2785 resolves this immediate
issue by moving 'ncurses/gpm' to (gnu packages ncurses), to eliminate
the non-delayed cross-module variable reference between
mutually-dependent modules.

FWIW, I would like to see us work to eliminate all cyclic module
dependencies in Guix, by splitting up our package modules as needed so
that they form a directed acyclic graph.

[*] In more detail, what Guile does is this: when asked to load module
A, if it already exists, it does nothing.  Otherwise, it immediately
creates module A as an empty module, and then starts loading it from the
top, starting with its 'define-module' form.  It begins by recursively
loading all modules imported by module A.  At this point, none of the
A's definitions have been loaded yet.  If, in the course of importing
those modules, a request is made to load module A (caused by a circular
dependency), Guile will see that module A already exists, so it does
nothing, although it is empty.  So, the order in which
mutually-dependent modules are populated depends on which module is
loaded first, and the order in which they import each other, etc.

    Regards,
      Mark

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Ricardo Wurmus]

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

> FWIW, I would like to see us work to eliminate all cyclic module
> dependencies in Guix, by splitting up our package modules as needed so
> that they form a directed acyclic graph.

(Note: this goes off on a tagent, but I think it is still relevant.)

I wonder if maybe having a single module per package might be the way to
go.  It may seem extreme and there’s an unwelcome bit of repetition by
declaring dependent modules *in addition* to declaring packages as
inputs — but it might also allow us to “freeze” or serialize a slice of
the package graph and store it alongside the store items.

What I envision is that you could use a much richer interface (namely
Scheme itself) to explore the package closure *long after* the package
has been installed to the store, instead of having to make do with the
rather poor representation of references in the database.  You would be
able to look at the section of the graph Guix describes that resulted in
the store item(s), untangle the graph in a REPL and even use that as a
starting point to create a package variant right inside the REPL without
having to check out an older version of Guix.

This is made more complicated by the fact that we don’t have a direct
mapping of packages to modules, which means that we don’t have a direct
map from store items to Guile ELF files that could be loaded in a REPL.

If we switched to defining a single package per module, however, I think
we need some syntactic sugar to avoid declaring dependencies more than
once.

--
Ricardo

GPG: BCA6 89B6 3655 3801 C3C6  2150 197A 5888 235F ACAC
https://elephly.net

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Ludovic Courtès]

Hi Mark,

I agree that it’s terrible that we have to deal with such problems.
Thanks for (re)explaining the issue.

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

> FWIW, I would like to see us work to eliminate all cyclic module
> dependencies in Guix, by splitting up our package modules as needed so
> that they form a directed acyclic graph.

This seems hard to achieve, unless we use one file per package.

Perhaps another option would be to introduce a ‘define-package’ form
that would thunk every package definition, or something like that,
though it wouldn’t help in more complex cases I guess.

Ludo’.

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Ricardo Wurmus]

Ludovic Courtès <ludo@gnu.org> skribis:

> Mark H Weaver <mhw@netris.org> skribis:
>
>> FWIW, I would like to see us work to eliminate all cyclic module
>> dependencies in Guix, by splitting up our package modules as needed so
>> that they form a directed acyclic graph.
>
> This seems hard to achieve, unless we use one file per package.

Are there drawbacks to using one file per package other than it’s a bit
“heavy” due to all the boilerplate of license headers and module
definitions?

--
Ricardo

GPG: BCA6 89B6 3655 3801 C3C6  2150 197A 5888 235F ACAC
https://elephly.net

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Danny Milosavljevic]

On Tue, 25 Jul 2017 23:28:38 +0200
Ricardo Wurmus <rekado@elephly.net> wrote:

> Are there drawbacks to using one file per package other than it’s a bit
> “heavy” due to all the boilerplate of license headers and module
> definitions?

Probably the NFS case gets much slower because of the gazillon stat() calls...

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Alex Sassmannshausen]

Ricardo Wurmus writes:

> Ludovic Courtès <ludo@gnu.org> skribis:
>
>> Mark H Weaver <mhw@netris.org> skribis:
>>
>>> FWIW, I would like to see us work to eliminate all cyclic module
>>> dependencies in Guix, by splitting up our package modules as needed so
>>> that they form a directed acyclic graph.
>>
>> This seems hard to achieve, unless we use one file per package.
>
> Are there drawbacks to using one file per package other than it’s a bit
> “heavy” due to all the boilerplate of license headers and module
> definitions?

I have two thoughts that are related to this:
- languages like Perl, which have tons of modules on CPAN, a great
  number of which are incredibly simple and small: we are literally
  talking about adding 100s of files. This is quite different from
  adding a "program", such as Emacs, a larger, well-defined definition.
  I don't think the Perl example is a stopper, but perhaps something to
  consider in terms of performance/implementation.

- If we take this direction, perhaps we should aim to have a helper
  commandline script to which you can pass the dependencies, and which
  takes care of writing the boilerplate as well as importing the
  appropriate modules?

Alex

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Ludovic Courtès]

Ricardo Wurmus <rekado@elephly.net> skribis:

> Ludovic Courtès <ludo@gnu.org> skribis:
>
>> Mark H Weaver <mhw@netris.org> skribis:
>>
>>> FWIW, I would like to see us work to eliminate all cyclic module
>>> dependencies in Guix, by splitting up our package modules as needed so
>>> that they form a directed acyclic graph.
>>
>> This seems hard to achieve, unless we use one file per package.
>
> Are there drawbacks to using one file per package other than it’s a bit
> “heavy” due to all the boilerplate of license headers and module
> definitions?

It’d be less convenient for packagers, notably because you’d have to
specify all the modules to import, as you noted before.  We could work
around it with a ‘define-package-module’ macro that would lookup
packages with ‘specification->package’ or something like that.

There might be other implications, I’m not sure.

Ludo’.

Re: Trouble with circular module dependencies (Re: 01/02: gnu: Add ncurses-with-gpm.)

[Danny Milosavljevic]

Hi Mark,

On Sun, 23 Jul 2017 18:22:39 -0400
Mark H Weaver <mhw@netris.org> wrote:

> any of us could make, invited by our IMO questionable practice of
> allowing cyclic module dependencies, and not sufficiently mitigated by
> warnings about this issue.

Sorry!

It was actually caused by me trying to avoid a dependency of (gnu packages ncurses) to (gnu packages linux).  But in trying to avoid it I made it worse.

I have to say this circular dependency stuff is quite... strange.  I'm not sure what it helps to have it in Guile at all.

But thanks for the explanation.  I've also looked at libguile/modules.c where it indeed first creates an empty module and only then resolves the imports (scm_c_define_module).

I've worked with languages which explicitly disallow module circular dependencies (Pascal etc) and it's not been constraining to me - on the contrary, it makes me better visualize which modules are more fundamental (in my reductionist worldview of a program).