soydepend-go

See soydepend-rs for Rust implementation

soydepend is a simple, Go generic map-based dependency graph implementation. It supports multi-dependencies, deep dependencies, autoremove features, etc.

Any comparable types can be used as nodes in soydepend.

Features

Features are usually implemented as methods of type Graph[T].

The type currently uses 3 hash maps to implement dependency graphs.

To address the ever-growing memory use by Go map memory leaks, soydepend provides Clone and Realloc for consumers to create an equivalent graph with lower memory allocation footprint.

• Depend or undepend arbitarily

  Users can arbitarily adds new dependencies to graph, so long that new dependencies do not violate any rules (e.g. circular dependency).

  Users can do something like this:

  func foo() {
    // New graph with string nodes
    g := soydepend.New[string]()
  
    _ = g.Depend("b", "a") // Nodes b and a are both initialized as it's inserted (b depends on a)
    _ = g.Depend("c", "b") // Node c gets initialized to depend on node b
  
    g.DependsOn("b", "a") // true
    g.DependsOn("c", "a") // true, via b
  }

  Dependent can undepend from any of its direct dependencies.

  func foo() {
    // New graph with string nodes
    g := soydepend.New[string]()
  
    _ = g.Depend("b", "a") // Nodes b and a are both initialized as it's inserted (b depends on a)
    _ = g.Depend("c", "b") // Node c gets initialized to depend on node b
  
    g.DependsOn("b", "a") // true
    g.DependsOn("c", "a") // true, via b
  
    g.Undepend("c", "a") // error, no direct dependency c->a
    g.Undepend("c", "b") // ok, c is now independent
  
    g.DependsOn("c", "b") // false
    g.DependsOn("c", "a") // false
  
    g.Undepend("c", "b") // error, no such dependency
  }

  Any circular dependencies, deep or direct, are prevented on insertion:

  func foo() {
    var err error
  
    g := soydepend.New[string]()
    err = g.Depend("b", "a") // ok: b -> a
    err = g.Depend("c", "b") // ok: c -> b
    err = g.Depend("d", "c") // ok: d -> c
  
    err = g.Depend("a", "d") // error! circular dependency! a -> d -> c -> b -> a
  }

• Auto-removal of dependencies and dependents

  soydepend provides many removal strategies:

  1. Remove (standard)

  Removes target nodes with 0 dependents

  func foo() {
    var err error
  
    g := soydepend.New[string]()
    _ =  g.Depend("b", "a")
    _ =  g.Depend("c", "b")
    _ =  g.Depend("d", "c")
  
    _ =  g.Remove("d") // ok: d has 0 dependents
    _ =  g.Remove("c") // ok: c now has 0 dependents (d was just removed)
  
    err = g.Remove("a") // error! 'a' still has dependent 'b'
  }

  2. RemoveForce

  Removes target as well as its dependents

  func foo() {
    g := soydepend.New[string]()
  
    _ = g.Depend("b", "a")
    _ = g.Depend("c", "b")
    _ = g.Depend("d", "c")
  
    g.RemoveForce("b") // removes b, c, and d
  }

  3. RemoveAutoRemove

  Removes target, as well as its dependents, as well as its dependencies whose only dependent is target. This is recursive, and works like how autoremove command works in package managers (e.g. apt autoremove <FOO>)

  func foo() {
    g := soydepend.New[string]()
  
    _ = g.Depend("b", "a")
    _ = g.Depend("c", "b")
    _ = g.Depend("d", "c")
    _ = g.Depend("x", "b")
    _ = g.Depend("y", "x")
  
    g.RemoveAutoRemove("y") // removes y and x
  }

• Topological sort order in layers

  Discover dependencies in layers (nodes in earlier layer will not depend on any nodes that appear in subsequent layer):

  func foo() {
    g := soydepend.New[string]()
  
    _ = g.Depend("b", "a")
    _ = g.Depend("c", "b")
    _ = g.Depend("d", "c")
    g.Layers() // [["a"], ["b"], ["c"], ["d"]]
    
    _ = g.Depend("x", "0")
    g.Layers() // [["0", "a"], ["b", "x"], ["c"], ["d"]]
  
    _ = g.Undepend("b", "a")
    g.Layers() // [["0", "a", "b"], ["x"], ["c"], ["d"]]
  
    _ = g.Depend("b", "c")
    g.Layers() // [["0", "a"], ["x"], ["c"], ["b", "d"]]
  }