Implement recursive addition

When both --add and --recursive options are supplied, the program
adds both the requested services and any services they depend upon.

* builtin.go (IsBuiltinServiceName): New function.
* initd.go (WhoProvides): New function.
* main.go: New option --recursive
(AddDependencies): New function.
(Add): Optionally use AddDependencies to complete the set of
services to add.
(reportCyclicDependencies): New function.
(Inc): Ignore services that are already present in the sequence.
* rcd.go (FindServiceByName): New function.

4 files changed, 130 insertions, 13 deletions

diff --git a/builtin.go b/builtin.go
index 79dbba0..ed83174 100644
--- a/builtin.go
+++ b/builtin.go
@@ -98,3 +98,12 @@ func BuiltinServiceIterator(start bool) ServiceIterator {
 		return &srv
 	}
 }
+
+func IsBuiltinServiceName(s string) bool {
+	for _, srv := range builtinServices {
+		if srv.BaseName() == s {
+			return true
+		}
+	}
+	return false
+}
diff --git a/initd.go b/initd.go
index e0f9569..24f54e3 100644
--- a/initd.go
+++ b/initd.go
@@ -59,6 +59,15 @@ func (d *InitDir) Iterator(sel NameSelector) ServiceIterator {
 	}
 }
 
+func (d *InitDir) WhoProvides(sym string) (result []Service) {
+	for _, srv := range d.service {
+		if (srv.Provides(sym)) {
+			result = append(result, NewRCService(srv))
+		}
+	}
+	return
+}
+
 // Given service base name, return a copy of the corresponding Service
 // structure.
 func (d *InitDir) FindServiceByName(name string) (Service, bool) {
diff --git a/main.go b/main.go
index bb73885..7501310 100644
--- a/main.go
+++ b/main.go
@@ -13,6 +13,7 @@ var opts struct {
 	List bool `long:"list" description:"List services"`
 	Add  bool `long:"add" description:"Add services"`
 	Del  bool `long:"del" description:"Delete services"`
+	Recurse bool `long:"recursive" short:"t" description:"Recursively process dependencies"`
 	LF func(string) `short:"l" long:"level" value-name:"L[L...]" description:"apply to these runlevels"`
 	Level []string 
 	RCDirectory string `short:"C" long:"rc.d" value-name:"DIR" default:"/etc/rc.d" description:"Path to the rc.d directory"`
@@ -375,6 +376,75 @@ func (s Symlink) Create() error {
 	return nil
 }
 
+// Return a sequence of services from srvin and all services they depend
+// on, ordered so that any given service precedes the services that depend
+// upon it.
+func (d *InitDir) AddDependencies(srvin []Service) (srvout []Service) {
+	srvmap := make(map[string]int)
+	for i := 0; i < len(srvin); {
+		srv := srvin[i]
+		if _, found := srvmap[srv.BaseName()]; found {
+			srvin = append(srvin[0:i], srvin[i+1:]...)
+			continue
+		} else {
+			srvmap[srv.BaseName()] = i
+			i++
+		}
+		for _, sym := range srv.RequiredStart() {
+			if IsBuiltinServiceName(sym) {
+				continue //FIXME
+			}
+			dep := d.WhoProvides(sym)
+			if (len(dep) > 0) {
+				// FIXME: Selecting first one. Better ideas?
+				srvin = append(srvin, dep[0])
+			} else {
+				Logger.Fatal(`unresolved symbol: `+sym)
+			}
+		}
+		// FIXME: Same for RequiredStop?
+	}
+
+	// Build dependency matrix
+	dm := NewDepmap(len(srvin))
+	for i, srv := range srvin {
+		for _, sym := range srv.RequiredStart() {
+			dm.Set(i, srvmap[d.WhoProvides(sym)[0].BaseName()])
+		}
+	}
+
+	// Compute transitive closure and shortest paths.  Report eventual
+	// cyclic dependencies.
+	p := dm.FindCycles()
+        reportCyclicDependencies(p, srvin)	
+
+	// Keep track of already processed services
+	srvind := make([]bool, dm.Dim())
+
+	// Build the output array
+	for i := 0; i < dm.Dim(); i++ {
+		for j := 0; j < dm.Dim(); j++ {
+			if dm.IsSet(i, j) {
+				path := dm.Path(i, j)
+				for k := len(path) - 1; k > 0; k-- {
+					n := path[k]
+					if !srvind[n] {
+						srvout = append(srvout,
+							        srvin[n])
+						srvind[n] = true
+					}
+				}
+			}
+		}
+		if !srvind[i] {
+			srvout = append(srvout, srvin[i])
+			srvind[i] = true
+		}
+	}
+	
+	return
+}
+
 func Add(args *ArgList) {
 	if args.Len() == 0 {
 		Logger.Fatal(`not enough arguments`)
@@ -393,18 +463,26 @@ func Add(args *ArgList) {
 	var rsStart Runlevels  // Start levels
 	var rsStop Runlevels   // Stop levels
 
-	// Collect services to be added and corresponding runlevels
+	// Collect services to be added
 	nextservice := initdir.Iterator(args.GetNameSelector())
 	srv := nextservice()
 	for srv != nil {
-		rsStart.Or(srv.DefaultStart())
-		rsStop.Or(srv.DefaultStop())
 		services = append(services, srv)
 		srv = nextservice()
 	}
 	// If any unused arguments remain, report them and exit.
 	args.Report()
 
+	if opts.Recurse {
+		services = initdir.AddDependencies(services)
+	}
+
+	// Compute the set of runlevels affected
+	for _, srv := range services {
+		rsStart.Or(srv.DefaultStart())
+		rsStop.Or(srv.DefaultStop())
+	}
+	
 	// Mask out non requested runlevels
 	rsStart.And(rsmask)
 	rsStop.And(rsmask)
@@ -426,15 +504,18 @@ func Add(args *ArgList) {
 		r = nextlevel()
 	}
 
-	// Create the array of symlinks to be created
+	// Array of symlinks to be created
 	var symlink []*Symlink
 	
 	// Incorporate each new service into the corresponding runlevels
 	for _, srv := range services {
+		if opts.Debug {
+			Logger.Printf("DEBUG: adding %s\n", srv.BaseName())
+		}
+		
 		nextlevel := rsStart.Iterator()
 		r := nextlevel()
 		for r.IsValid() {
-//			fmt.Printf("Level %s start:\n", r.Letter())
 			if s := rcdir[r.Index()].Start.Inc(srv); s != nil {
 				symlink = append(symlink, s)
 			}
@@ -444,7 +525,6 @@ func Add(args *ArgList) {
 		nextlevel = rsStop.Iterator()
 		r = nextlevel()
 		for r.IsValid() {
-//			fmt.Printf("Level %s stop:\n", r.Letter())
 			if s := rcdir[r.Index()].Stop.Inc(srv); s != nil {
 				symlink = append(symlink, s)
 			}
@@ -563,24 +643,32 @@ func (rseq *RCSeq) TraverseEquidependentServices(n int) ServiceIterator {
 	}
 }				
 
-// Detect and report possible cyclic dependencies.
-func (rseq *RCSeq) DetectRecursion() {
-	p := rseq.Deps.Copy().FindCycles()
+func reportCyclicDependencies(p [][]int, srv []Service) {
 	if len(p) > 0 {
 		Logger.Printf("Cyclic dependencies detected:\n")
 		for _, t := range p {
 			s := make([]string, len(t))
 			for i, n := range t {
-				s[i] = rseq.Service[n].BaseName()
+				s[i] = srv[n].BaseName()
 			}
 			Logger.Printf("%s\n", strings.Join(s, ` -> `))
 		}
 		os.Exit(1)
 	}
+}	
+
+// Detect and report possible cyclic dependencies.
+func (rseq *RCSeq) DetectRecursion() {
+	reportCyclicDependencies(rseq.Deps.Copy().FindCycles(),
+			         rseq.Service)
 }
 
-// Incorporate service newsrv into sequence rseq
+// Incorporate service newsrv into sequence rseq.
 func (rseq *RCSeq) Inc(newsrv Service) *Symlink {
+	if s := rseq.FindServiceByName(newsrv.BaseName()); s != nil {
+		return nil
+	}
+	
 	/* 1. Register newserv in rsec. Let N be its number.
            2. Compute dependency matrix
            3. Compute priority for the new service:
@@ -589,7 +677,7 @@ func (rseq *RCSeq) Inc(newsrv Service) *Symlink {
            3.2. Traverse the Nth row of the matrix.
                  For each element (i,j) that is true, set
 
-                    prio = update(prio, srv[j].prio
+                    prio = update(prio, srv[j].prio)
 
                  where update is max for start sequence and min for stop.
            4. Create symlink name and return new Symlink structure.
diff --git a/rcd.go b/rcd.go
index 8ce3faf..39f1266 100644
--- a/rcd.go
+++ b/rcd.go
@@ -78,7 +78,9 @@ func (seq *RCSeq) BuildDependencies() {
 				}
 			}
 			if ! found && seq.Isstart {
-				Logger.Printf("%s: dependency %s not found in runlevel %s\n", dependency.BaseName(), sym,
+				Logger.Printf("%s: dependency %s not found in runlevel %s\n",
+					      dependency.BaseName(),
+					      sym,
 					      seq.dir.runlevel.Letter())
 				seq.Deps.Set(i, 0)
 			}
@@ -102,6 +104,15 @@ func (seq *RCSeq) SysVServiceIterator() ServiceIterator {
 	}
 }
 
+func (seq *RCSeq) FindServiceByName(name string) Service {
+	for _, srv := range seq.Service {
+		if srv.BaseName() == name {
+			return NewRCService(srv)
+		}
+	}
+        return nil
+}
+
 // Create a RC sequence corresponding to the directory rcd.
 // RSEQ must be either rcd.Start or rcd.Stop.
 func (rseq *RCSeq) InitRCSeq(rcd *RCDir) {