[Mageia-dev] Fwd: [Cooker] WANTED: the cyclic dependency Hell (aka Automated Bootstrapping)

Mon Oct 17 11:57:56 CEST 2011

Did anyone see this? this sounds very interesting imho...
+
+----------  Doorgestuurd bericht  ----------
+
+Onderwerp: [Cooker] WANTED: the cyclic dependency Hell (aka Automated 
+Bootstrapping)
+Datum: maandag 17 oktober 2011, 11:32:08
+Van: Franck Bui <franck.bui at mandriva.com>
+Aan: maintainers at mandriva.com, cooker at mandrivalinux.org
+CC: Jeff Johnson <n3npq at mac.com>
+
+Hi Folks,
+
+,----[ Preface ]
+| This is boring material simply because its main purpose is overall
+| quality improvement. But please keep on reading and contribute ! :)
+`----
+
+,----[ Disclaimer ]
+| I'm far from being an expert packager, actually it's quite the
+| opposite, so I'm probably saying a lot of obvious things, sorry again
+| for being boring.
+`----
+
+Table of Contents
+=================
+1 Bootstrapping 
+2 Cyclic dependencies 
+    2.1 Reasons 
+3 "Digraph" tool 
+    3.1 Goals 
+    3.2 Examples 
+4 "Digraph" application to Cooker main/release media 
+    4.1 First inconsistencies 
+        4.1.1 Example 1 
+        4.1.2 Example 2 
+        4.1.3 Example 3 
+    4.2 Get all of them 
+    4.3 Results 
+5 Conclusion 
+
+
+1 Bootstrapping 
+~~~~~~~~~~~~~~~~
+
+Bootstrapping cooker into a new architecture (or even into the same arch
+but with a new but incompatible ABI) is currently a pain and takes an
+insane amount of time (ask to pcpa for gory details :).
+
+First, what's a bootstrap ? It's the different steps/stages taken to
+rebuild all packages into a new ABI using a) some packages built for
+the old ABI (mostly the toolchain for cross compiling a very small set
+of programs to create a basic native rootfs) b) the package sources
+which are going to be build natively.
+
+Having an automated bootstrapping not only means less pain to switch to
+a new ABI but it also means that the distro is in a good shape since the
+bootstrap requires a consistent repository, no more cyclic dependence
+between packages, etc...
+
+Eventually having an automated bootstrapping means that the process is a
+repeatable and deterministic one. Since this process is pretty sensible
+to the coherency state of the distro, it could be run regularly to catch
+any new regressions.
+
+How are packages being built during the bootstrapping ?
+
+Let say that we want to build 'A' package. 'A' has a build-require on
+'B' which in its turn has a build-require on 'C': A -> B -> C
+
+To build/install 'A.rpm', we should:
+
+  - see if 'C.rpm' is already installed. If so then go to the next item
+    otherwise we have to build/install 'C.rpm' first (from C.src.rpm).
+
+  - Same as previous item but with 'B.rpm'.
+
+  - Finally build and install 'A.rpm'.
+
+Note: that both the build and the install steps have their own deps.
+
+You may think it's not that different from what's happening when you
+submit a package to the build-system. But it is simply because we start
+with an _empty_ rpm database. This means that when a build requirement
+is missing, rpm likely won't find the BR's binary package installed.
+Therefore the build-require will be considered for a build in its turn
+and so on.
+
+2 Cyclic dependencies 
+~~~~~~~~~~~~~~~~~~~~~~
+
+At this point you probably guess why the automated bootstrapping is
+currently not possible: the reason is: "cyclic dependencies".
+
+How are they created ?
+
+2.1 Reasons 
+============
+
+Here are the main reasons I could see:
+
+ 1/ Each package has build requirements specific to the generation of
+    the documentation that the package ships amongst the binaries.
+    Unfortunately tools used to generate documentation such as doxygen,
+    tex... are pretty 'high-level' tools and they require themself a
+    lot of other packages (having their own docs) to be built first.
+
+ 2/ Some packages provides a main functionality with light
+    requirements but also some additional/minor functionalities
+    (sometimes not use at all) with some strong requirements. Such
+    packages may be considered for being splitted. You can take a look
+    to libidn package for an example.
+
+ 3/ Some packages 'pull' a huge build dependency just for building a
+    useless module/example-code. For example, 'libalsa2' has a
+    buildrequires on python-devel simply in order to build a (useless)
+    python module example which won't be used at all.
+
+By far, the more problematic item is 1/. The reason is that it's
+currently not possible to disable easily the doc generation hence
+removing the associated requirements. Most of the packages are
+affected.
+
+Item 2/ and 3/ are less important IMO because they depend on
+packager's taste only. Moreover there should be many less packages
+following into these 2 categories.
+
+Therefore I think we should first focus on 1/. I'll try to come up
+with a simple/naive proposition in a next post mostly in order to
+initiate a reflexion on this subject.
+
+3 "Digraph" tool 
+~~~~~~~~~~~~~~~~~
+
+Back to the cycle dependencies.
+
+As you know, all package relations can be represented by a directed
+graph.  I wrote a basic tool which can be used to operate on directed
+graph: [https://github.com/fbuihuu/digraph].
+
+3.1 Goals 
+==========
+
+The tool is in a very early stage and probably will stay as it is. But
+it can be used to:
+
+  - find all cycles in a graph.
+
+  - group each cycle into a single node making the resulting graph
+    (called condensation graph) acyclic.
+
+  - do a topological sort on an acyclic graph. This means that the tool
+    is able to tell you the order of the packages to be built.
+
+  - visualize graph with the help of graphviz.
+
+You simply need to describe the graph first in a text file. For an
+example, have a look to graph.txt, the syntax used is obvious.
+
+3.2 Examples 
+=============
+
+This file gives an example of a graph description that can be visualized
+here:
+
+  [http://mes5devel.mandriva.com/~fbui/graph/graph1.pdf]
+
+Once your graph description is ready you can feed the tool with it:
+
+  $ ./digraph.py graph.txt
+  Connected components:
+  --------------------
+  * Group(c - 2): c, d
+  * Group(g - 2): g, f
+  * Group(y - 2): y, x
+  * Group(a - 3): a, b, e
+
+The tool by default shows you the cyclic groups (aka "strongly connected
+components").
+
+If you want other information then you'll need to hack the current
+script but it's quite trivial to do so. See main() for a couple of
+examples.
+
+For example, you can create the condensation of the previous graph and
+ask it to plot it. Here's the result:
+
+  [http://mes5devel.mandriva.com/~fbui/graph/graph2.pdf]
+
+Or you can get a compact view to represent each group by a single
+node:
+
+  [http://mes5devel.mandriva.com/~fbui/graph/graph3.pdf]
+
+Eventually you can ask to the tool to do a topological sort of the
+nodes. Here's the result:
+
+  Topological order:
+  -----------------
+  h -> j -> Group(g - 2) -> Group(c - 2) -> Group(a - 3) -> i -> Group(y - 2)
+
+4 "Digraph" application to Cooker main/release media 
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+As you probably guess, the purpose of this script is mainly for its
+application to the distro.
+
+The fist step is to generate a description of the packages relationship
+in cooker. The following script exactly do that:
+
+  [http://mes5devel.mandriva.com/~fbui/graph/dump-rpmdeps.py]
+
+How ? It simply parses a set of .rpm files, extracts some info such as
+the "requires:" and "provides:" tags and retrieve the src.rpm used to
+generate the .rpm. From the source package it extracts the
+"buildrequires:" tags. With those information, it dumps the dependencies
+into a description format used by "digraph" tool.
+
+BTW, if someone can figure out a faster method for achieving this, I'm
+listening :). It's currently slow mainly because it uses "urpmq
+--sourcerpm <rpm>" to extract the source package filename. If someone
+can figure out another mean with rpm(8) to do that...
+
+4.1 First inconsistencies 
+==========================
+
+Running "dump-rpmdeps.py" script shows the first repository's
+inconsistencies. Following are some examples:
+
+4.1.1 Example 1 
+----------------
+
+  Warning: source not found: 
+/mnt/BIG/devel/cooker/SRPMS/main/release/ant-1.8.2-4.src.rpm (referenced by 
+ant-commons-logging)
+
+In this case, the name of the source rpm is not exact since the file in
+the SRPMS directory that can be found is "ant-1.8.2-4.1.src.rpm".
+
+4.1.2 Example 2 
+----------------
+
+  Warning: unknown alias 'sepol-static-devel' used by 'libselinux'
+
+In this case 'libselinux' refers to 'sepol-static-devel' package which
+doesn't seem to exist, at least in the main/release media.
+
+4.1.3 Example 3 
+----------------
+
+  Warning: unknown alias 'geronimo-jta-1.0.1B-api' used by 'jakarta-commons-
+transaction'
+
+'jakarta-commons-transaction' (in main/release) has a buildrquires on
+'geronimo-jta-1.0.1B-api', which is in contrib media.
+
+4.2 Get all of them 
+====================
+
+For a full list of such inconsistencies, please see:
+
+  [http://mes5devel.mandriva.com/~fbui/graph/cooker-inconsistencies.log]
+
+4.3 Results 
+============
+
+This description can now be used it with "digraph" to see if there're
+some cycles and if so what they look like:
+
+  $ ./digraph.py cooker-i586-dependencies.txt
+  Connected components:
+  --------------------
+  * Group(asm2 - 2): asm2, objectweb-anttask
+  * Group(python-sphinx - 2): python-sphinx, python-nose
+  * Group(nant - 2): log4net, nant
+  * Group(gnome-js-common - 2): gnome-js-common, seed
+  * Group(vcdimager - 3): vcdimager, libcdio, libcddb
+  * Group(perl-Moose - 5): perl-Moose, perl-Test-Warn, perl-Array-Compare, 
+perl-Package-DeprecationManager, perl-Package-Stash
+  * Group(ant - 461): flac, drakx-kbd-mouse-x11, xcb-util, gd, recode, gdbm, 
+poppler, strigi, libxp, libsndfile, ...
+
+So "only" 7 cycles, BUT the last one involves 461 packages ! And the
+reason is mainly "documentation generation".
+
+You can visualize those cycles, except the last one, by looking at the
+cyclic-*.pdf files at:
+
+  [http://mes5devel.mandriva.com/~fbui/graph/]
+
+5 Conclusion 
+~~~~~~~~~~~~~
+
+Please help to nuke this crazy dependency hell !
+
+The most important task IMHO is the need to find out how the
+documentation generation can be separated/disabled properly.
+
+Note that disabling generation of documentation is not only
+interesting for automated bootstrapping but also for architectures
+(such as ARM) which targets embedded devices with limited disk
+spaces.
+
+Also if the first inconsistencies found by the dumb tool are revelant,
+we want develop more sanity checkers and run them regularly to trap
+any new regressions introduced later.
+
+
+-------------------------------------------------------
+