7.4.2 Runlevels, part one

I came up with the following method (here in Pseudo-Scheme), which is possibly slightly buggy, but should give you the idea:

;; Beginning with the canonical names in CURRENT-SERVICES, start and
;; stop services until getting into a state where everything requested
;; in TARGET-SERVICES (which does not only consist of canonical names)
;; is provided, and the things they depends on, but no more.
(define (switch-runlevel current-services target-services)
  (let ((target-services-backup target-services)
	(unstartable '()))
    (let retry ()
      (repeat-until-none-of-these-changes-annythig
       ;; Replace all of them with canonical names which provide them.
       (canonicalize-names! target-services unstartable current-services)
       ;; Add what we need additionally.
       (add-dependencies! target-services unstartable current-services))
      (remove-redundancy! target-services)
      (stop-all-unneeded target-services)
      (catch 'service-could-not-be-started
	     (lambda ()
	       ;; Iterate over the list, starting only those which
	       ;; have all dependencies already resolved, so nothing
	       ;; we don't want will be started.  Repeat until done.
	       (carefully-start target-services))
	     (lambda (key service)
	       (set! unstartable (cons service unstartable))
	       (set! target-services backup-target-services)
	       (set! current-services (compute-current-services))
	       (retry))))))

This indeed looks like a nice way to get what we want. However, the details of this are not as easy as it looks like. When replacing virtual services with canonical names, we have to be very careful. Consider the following situation:

The virtual service X is provided by both A and B, while Y is provided only by B. We want to start C (which depends on X) and D (which depends on Y). Obviously we should use B to fulfill the dependency of C and D on X and Y, respectively. But when we see that we need something that provides X, we are likely to do the wrong thing: Select A. Thus, we need to clean this up later. I wanted to do this as follows:

While substituting virtual services with canonical names, we also safe which one we selected to fulfill what, like this:

((A . (X))
 (B . (Y)))

Later we look for conflicts, and as A and B conflict, we look which one can be removed (things they provide but are not required by anyone should be ignored, thus we need to create a list like the above). In this case, we can replace A with B as B also provides X (but A does not provide Y, thus the reverse is impossible). If both could be used, we probably should decide which one to use by looking at further conflicts, which gets pretty hairy. But, in this case, we are lucky and end up with this:

((B . (X Y)))

This way of finding out which service we should use in case of conflicts sounds pretty sane, but if you think it will work well, you have been fooled, because actually it breaks horribly in the following situation:

If we need all of W, X, Y and Z, then obviously we need to take C and D. But if we have a list like this, we cannot fix it:

((A . (W X Y))
 (B . (Z)))

Thus, we cannot do it this way.