resolver

README

dependency-resolver

Small library that helps in determining the order of applying any items that are dependent upon others. It also detects when there are circular dependencies.

Common use cases:

• Given a set of computing infrastructure resources, determine the order in which these resources should be created/modified.
• Generating a dependency tree of a software's third-party packages.

Example Usage

import (
    dependencyresolver "gitlab.com/climactech/dependency-resolver"
)

func main() {
    resolver := dependencyresolver.NewEngine()

    // Express the item connections. Here, we will use this sample tree:
    // (A depends on C and D, C depends on G, D depends on E, etc.)
    //
    //    |-> C -> G -|
    // A -|        |  |
    //    |-> D -| |  |
    //           | |  |
    //    |-> E <--|  |
    // B -|           |
    //    |-> F <-----|    
    //
    resolver.AddDependency("A", "C")
    resolver.AddDependency("A", "D")
    resolver.AddDependency("B", "E")
    resolver.AddDependency("B", "F")
    resolver.AddDependency("C", "G")
    resolver.AddDependency("D", "E")
    resolver.AddDependency("E", "G")
    resolver.AddDependency("G", "F")

    // Notice that "F" has no dependencies,  so we did not add a call for it

    // Now, order the items in the order in which they should be processed

    orderResult := resolver.Order()

    // At this point, orderResult.Items() will have the list of processing
    // stages and items for each stage. orderResult.Items will contain the
    // following items:
    //
    // 1: F (F is the only item with no dependencies, so naturally this must be processed first)
    // 2: G
    // 3: C, E (these two can be processed either serially or in parallel at this point)
    // 4: B, D
    // 5: A (A depended on everything else, so naturally it's the last item that should be processed)
}

Copyright

Copyright © 2023-2024 Climactech, LLC

Documentation

Overview

Package dependency-resolver implements a dependency resolution engine for interconnected items/resources.

Example

package main

import (
	"fmt"
	"slices"
	"strings"

	dependencyresolver "gitlab.com/climactech/dependency-resolver"
)

func main() {
	resolver := dependencyresolver.NewEngine()
	stage := 0

	// Express the item connections. Here, we will use this sample tree:
	// (A depends on C and D, C depends on G, D depends on E, etc.)
	//
	//    |-> C -> G -|
	// A -|        |  |
	//    |-> D -| |  |
	//           | |  |
	//    |-> E <--|  |
	// B -|           |
	//    |-> F <-----|
	//
	resolver.AddDependency("A", "C")
	resolver.AddDependency("A", "D")
	resolver.AddDependency("B", "E")
	resolver.AddDependency("B", "F")
	resolver.AddDependency("C", "G")
	resolver.AddDependency("D", "E")
	resolver.AddDependency("E", "G")
	resolver.AddDependency("G", "F")

	// Notice that "F" has no dependencies,  so we did not add a call for it

	// Now, order the items in the order in which they should be processed

	orderResult := resolver.Order()

	for items := range orderResult.Items() {
		if stage > 0 {
			fmt.Print(" -> ")
		}

		slices.Sort(items)
		fmt.Print(strings.Join(items, ", "))
		stage++
	}

	fmt.Print("\n")

}

Output:

F -> G -> C, E -> B, D -> A

Example (CircularDependencyDetection)

package main

import (
	"fmt"
	"strings"

	dependencyresolver "gitlab.com/climactech/dependency-resolver"
)

func main() {
	var (
		addResult dependencyresolver.AddResult
		err       error
	)

	sampleItems := [][]string{
		{"A", "C"},
		{"A", "D"},
		{"B", "E"},
		{"B", "F"},
		{"C", "G"},
		{"D", "E"},
		{"E", "G"},
		{"F", "A"},
		{"G", "F"}, // this creates a circular dependency!
	}

	resolver := dependencyresolver.NewEngine()

	for _, connection := range sampleItems {
		if addResult, err = resolver.AddDependency(connection[0], connection[1]); err != nil {
			fmt.Printf(
				"Found circular dependency when specifying '%s' as a dependency of '%s'\n",
				connection[1], connection[0],
			)

			// You can find the path of the circular dependency using
			// CircularDependencyPath. This path is nondeterministic.
			if false {
				fmt.Println(strings.Join(addResult.CircularDependencyPath, " --> "))
			}

			break
		}
	}

}

Output:

Found circular dependency when specifying 'F' as a dependency of 'G'

Index

• Variables
• type AddResult
• type Engine
  • func NewEngine() *Engine
  • func (e *Engine) AddDependency(parent string, dependency string) (AddResult, error)
  • func (e *Engine) Order() *OrderResult
• type OrderResult
  • func (o *OrderResult) Err() error
  • func (o *OrderResult) Items() <-chan []string

Examples

• Package
• Package (CircularDependencyDetection)

Variables

var ErrCircularDependency = errors.New("encountered circular dependency")

Types

type AddResult

type AddResult struct {
	// CircularDependencyPath contains the path of a circular dependency path.
	// The first and last items will be the same.
	CircularDependencyPath []string
}

AddResult contains the results of an AddDependency call.

type Engine

type Engine struct {
	// contains filtered or unexported fields
}

Engine is the dependency resolution engine.

func NewEngine

func NewEngine() *Engine

NewEngine creates and returns a new dependency resolution engine.

func (*Engine) AddDependency

func (e *Engine) AddDependency(parent string, dependency string) (AddResult, error)

AddDependency indicates that `dependency` is a dependency of `parent`.

func (*Engine) Order

func (e *Engine) Order() *OrderResult

Order sorts the items in the order that they should be processed.

type OrderResult

type OrderResult struct {
	// contains filtered or unexported fields
}

OrderResult contains the results of an Order call.

func (*OrderResult) Err

func (o *OrderResult) Err() error

Err returns the error, if any, that was encountered during iteration.

func (*OrderResult) Items

func (o *OrderResult) Items() <-chan []string

Items contains the items sorted in the order in which they should be processed.

Each main row can be thought of as the processing stage, and within each stage will be the items that can be processed, either serially or in parallel.