func ResolveStageFuncsOrder()

in newt/sysinit/sysinit.go [124:234]
82 lines of code
18 McCabe index (conditional complexity)

func ResolveStageFuncsOrder(sfs []stage.StageFunc) ([]stage.StageFunc, error) {
	var nodes []*stage.StageFunc
	var nodesQ []*stage.StageFunc
	nodesByStage := make(map[int][]*stage.StageFunc)
	nodesByName := make(map[string]*stage.StageFunc)

	for idx, _ := range sfs {
		sfRef := &sfs[idx]
		nodesByName[sfRef.Name] = sfRef
		if len(sfRef.Stage.Befores) == 0 && len(sfRef.Stage.Afters) == 0 {
			stage, _ := sfRef.Stage.IntVal()
			nodesByStage[stage] = append(nodesByStage[stage], sfRef)
		} else {
			nodesQ = append(nodesQ, sfRef)
		}
	}

	var stages []int
	for stage := range nodesByStage {
		stages = append(stages, stage)
	}
	sort.Ints(stages)

	// Lexicographically sort nodes in each stage, then build the nodes stack.
	// This helps ensure that sysinit order is reproducable and deterministic
	for stageIndex, _ := range stages {
		lsfs := nodesByStage[stages[stageIndex]]
		sort.Slice(lsfs, func(i int, j int) bool {
			a := lsfs[i]
			b := lsfs[j]

			if strings.Compare(a.Name, b.Name) == -1 {
				return false
			}
			return true
		})
		nodes = append(nodes, nodesByStage[stages[stageIndex]]...)
	}

	sort.Slice(nodesQ, func(i int, j int) bool {
		a := nodesQ[i]
		b := nodesQ[j]

		if strings.Compare(a.Name, b.Name) == -1 {
			return false
		}
		return true
	})
    
	// Put nodes without stages first, so they are resolved and put to
	// stack first - we do not want them to precede all nodes with stages.
	// While technically correct, it's better not to start sysinit with
	// nodes that do not have any stage since this will likely happen
	// before os init packages.
	nodes = append(nodesQ, nodes...)

	// Add implicit dependencies for nodes with stages. We need to add
	// direct dependencies between each node of stage X to each node of
	// stage Y to make sure they can be resolved properly and reordered
	// if needed due to other dependencies.
	sfsPrev := nodesByStage[stages[0]]
	stages = stages[1:]
	for _, stage := range stages {
		sfsCurr := nodesByStage[stage]

		for _, sfsP := range sfsPrev {
			for _, sfsC := range sfsCurr {
				sfsP.Deps = append(sfsP.Deps, sfsC)
				// Keep separate list of implicit dependencies
				// This is only used for Graphviz output
				sfsP.DepsI = append(sfsP.DepsI, sfsC)
			}
		}

		sfsPrev = sfsCurr
	}

	// Now add other dependencies, i.e. $after and $before
	for _, sf := range nodesQ {
		for _, depStr := range sf.Stage.Afters {
			depSf := nodesByName[depStr]
			if depSf == nil {
				return []stage.StageFunc{},
					util.FmtNewtError("Unknown depdendency (\"%s\") for \"%s (%s)\".",
						depStr, sf.Name, sf.Pkg.FullName())
			}
			depSf.Deps = append(depSf.Deps, sf)
		}
		for _, depStr := range sf.Stage.Befores {
			depSf := nodesByName[depStr]
			if depSf == nil {
				return []stage.StageFunc{},
					util.FmtNewtError("Unknown depdendency (\"%s\") for \"%s (%s)\".",
						depStr, sf.Name, sf.Pkg.FullName())
			}
			sf.Deps = append(sf.Deps, depSf)
		}
	}

	// Now we can resolve order of functions by sorting dependency graph
	// topologically. This will also detect circular dependencies.
	sfs = []stage.StageFunc{}
	for _, sfRef := range nodes {
		err := stageFuncResolve(sfRef, &sfs)
		if err != nil {
			return []stage.StageFunc{}, err
		}
	}

	return sfs, nil
}