doc: Add a "Boostrapping" section.

* doc/guix.texi (Package Modules): New node, with material formerly
  under "GNU Distribution".
  (Bootstrapping): New node.
* Makefile.am (EXTRA_DIST): Add doc/images/bootstrap-graph.dot and
  doc/images/bootstrap-graph.eps.
  (infoimagedir, dist_infoimage_DATA, DOT_OPTIONS): New variable.
  (.dot.png, .dot.eps, doc/guix.pdf, doc/guix.info, doc/guix.ps): New
  targets.
* doc/images/bootstrap-graph.dot: New file.

1 files changed, 154 insertions, 14 deletions

diff --git a/doc/guix.texi b/doc/guix.texi
index 23e8351c02..4d674b1b20 100644
--- a/doc/guix.texi
+++ b/doc/guix.texi
@@ -1426,28 +1426,168 @@ guix package}):
 guix package --list-available
 @end example
 
-The package definitions of the distribution may are provided by Guile
-modules in the @code{(gnu packages ...)} name space---for instance, the
-@code{(gnu packages emacs)} module exports a variable named
-@code{emacs}, which is bound to a @code{<package>} object
-(@pxref{Defining Packages}).  The @code{(gnu packages)} module provides
-facilities for searching for packages.
+Our goal is to build a practical 100% free software distribution of
+Linux-based and other variants of GNU, with a focus on the promotion and
+tight integration of GNU components, and an emphasis on programs and
+tools that help users exert that freedom.
+
+@menu
+* Package Modules::             Packages from the programmer's viewpoint.
+* Bootstrapping::               GNU/Linux built from scratch.
+@end menu
+
+Building this distribution is a cooperative effort, and you are invited
+to join!  @ref{Contributing}, for information about how you can help.
+
+@node Package Modules
+@section Package Modules
+
+From a programming viewpoint, the package definitions of the
+distribution are provided by Guile modules in the @code{(gnu packages
+...)} name space---for instance, the @code{(gnu packages emacs)} module
+exports a variable named @code{emacs}, which is bound to a
+@code{<package>} object (@pxref{Defining Packages}).  The @code{(gnu
+packages)} module provides facilities for searching for packages.
 
 The distribution is fully @dfn{bootstrapped} and @dfn{self-contained}:
 each package is built based solely on other packages in the
 distribution.  The root of this dependency graph is a small set of
 @dfn{bootstrap binaries}, provided by the @code{(gnu packages
-bootstrap)} module.  These are statically-linked binaries of the core
-tools without which building anything at all would be impossible.
+bootstrap)} module.  More on this in the next section.
+
+
+@node Bootstrapping
+@section Bootstrapping
+
+@c Adapted from the ELS 2013 paper.
+
+@cindex bootstrapping
+
+Bootstrapping in our context refers to how the distribution gets built
+``from nothing''.  Remember that the build environment of a derivation
+contains nothing but its declared inputs (@pxref{Introduction}).  So
+there's an obvious chicken-and-egg problem: how does the first package
+get built?  How does the first compiler get compiled?  Note that this is
+a question of interest only to the curious hacker, not to the regular
+user, so you can shamelessly skip this section if you consider yourself
+a ``regular user''.
+
+@cindex bootstrap binaries
+The GNU system is primarily made of C code, with libc at its core.  The
+GNU build system itself assumes the availability of a Bourne shell and
+command-line tools provided by GNU Coreutils, Awk, Findutils, `sed', and
+`grep'.  Furthermore, build programs---programs that run
+@code{./configure}, @code{make}, etc.---are written in Guile Scheme
+(@pxref{Derivations}).  Consequently, to be able to build anything at
+all, from scratch, Guix relies on pre-built binaries of Guile, GCC,
+Binutils, libc, and the other packages mentioned above---the
+@dfn{bootstrap binaries}.
+
+These bootstrap binaries are ``taken for granted'', though we can also
+re-create them if needed (more on that later.)
+
+@unnumberedsubsec Preparing to Use the Bootstrap Binaries
+
+@c As of Emacs 24.3, Info-mode displays the image, but since it's a
+@c large image, it's hard to scroll.  Oh well.
+@image{images/bootstrap-graph,,,Dependency graph of the early bootstrap derivations}
+
+The figure above shows the very beginning of the dependency graph of the
+distribution, corresponding to the package definitions of the @code{(gnu
+packages bootstrap)} module.  At this level of detail, things are
+slightly complex.  First, Guile itself consists of an ELF executable,
+along with many source and compiled Scheme files that are dynamically
+loaded when it runs.  This gets stored in the @file{guile-2.0.7.tar.xz}
+tarball shown in this graph.  This tarball is part of Guix's ``source''
+distribution, and gets inserted into the store with @code{add-to-store}
+(@pxref{The Store}).
 
+But how do we write a derivation that unpacks this tarball and adds it
+to the store?  To solve this problem, the @code{guile-bootstrap-2.0.drv}
+derivation---the first one that gets built---uses @code{bash} as its
+builder, which runs @code{build-bootstrap-guile.sh}, which in turn calls
+@code{tar} to unpack the tarball.  Thus, @file{bash}, @file{tar},
+@file{xz}, and @file{mkdir} are statically-linked binaries, also part of
+the Guix source distribution, whose sole purpose is to allow the Guile
+tarball to be unpacked.
+
+Once @code{guile-bootstrap-2.0.drv} is built, we have a functioning
+Guile that can be used to run subsequent build programs.  Its first task
+is to download tarballs containing the other pre-built binaries---this
+is what the @code{.tar.xz.drv} derivations do.  Guix modules such as
+@code{ftp-client.scm} are used for this purpose.  The
+@code{module-import.drv} derivations import those modules in a directory
+in the store, using the original layout.  The
+@code{module-import-compiled.drv} derivations compile those modules, and
+write them in an output directory with the right layout.  This
+corresponds to the @code{#:modules} argument of
+@code{build-expression->derivation} (@pxref{Derivations}).
+
+Finally, the various tarballs are unpacked by the
+derivations @code{gcc-bootstrap-0.drv}, @code{glibc-bootstrap-0.drv},
+etc., at which point we have a working C tool chain.
+
+
+@unnumberedsubsec Building the Build Tools
+
+@c TODO: Add a package-level dependency graph generated from (gnu
+@c packages base).
+
+Bootstrapping is complete when we have a full tool chain that does not
+depend on the pre-built bootstrap tools discussed above.  This
+no-dependency requirement is verified by checking whether the files of
+the final tool chain contain references to the @file{/nix/store}
+directories of the bootstrap inputs.  The process that leads to this
+``final'' tool chain is described by the package definitions found in
+the @code{(gnu packages base)} module.
+
+@c See <http://lists.gnu.org/archive/html/gnu-system-discuss/2012-10/msg00000.html>.
+The first tool that gets built with the bootstrap binaries is
+GNU Make, which is a prerequisite for all the following packages.
+From there Findutils and Diffutils get built.
+
+Then come the first-stage Binutils and GCC, built as pseudo cross
+tools---i.e., with @code{--target} equal to @code{--host}.  They are
+used to build libc.  Thanks to this cross-build trick, this libc is
+guaranteed not to hold any reference to the initial tool chain.
+
+From there the final Binutils and GCC are built.  GCC uses @code{ld}
+from the final Binutils, and links programs against the just-built libc.
+This tool chain is used to build the other packages used by Guix and by
+the GNU Build System: Guile, Bash, Coreutils, etc.
+
+And voilà!  At this point we have the complete set of build tools that
+the GNU Build System expects.  These are in the @code{%final-inputs}
+variables of the @code{(gnu packages base)} module, and are implicitly
+used by any package that uses @code{gnu-build-system} (@pxref{Defining
+Packages}).
+
+
+@unnumberedsubsec Building the Bootstrap Binaries
+
+Because the final tool chain does not depend on the bootstrap binaries,
+those rarely need to be updated.  Nevertheless, it is useful to have an
+automated way to produce them, should an update occur, and this is what
+the @code{(gnu packages make-bootstrap)} module provides.
+
+The following command builds the tarballs containing the bootstrap
+binaries (Guile, Binutils, GCC, libc, and a tarball containing a mixture
+of Coreutils and other basic command-line tools):
 
-Our goal is to build a practical 100% free software distribution of
-Linux-based and other variants of GNU, with a focus on the promotion and
-tight integration of GNU components, and an emphasis on programs and
-tools that help users exert that freedom.
+@example
+guix build bootstrap-tarballs
+@end example
+
+The generated tarballs are those that should be referred to in the
+@code{(gnu packages bootstrap)} module mentioned at the beginning of
+this section.
+
+Still here?  Then perhaps by now you've started to wonder: when do we
+reach a fixed point?  That is an interesting question!  The answer is
+unknown, but if you would like to investigate further (and have
+significant computational and storage resources to do so), then let us
+know.
 
-Building this distribution is a cooperative effort, and you are invited
-to join!  @ref{Contributing}, for information about how you can help.
 
 @c *********************************************************************
 @node Contributing