dag

package module
Version: v0.0.0-...-3804bac Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 26, 2021 License: MPL-2.0 Imports: 8 Imported by: 1

README

dag

This is a slightly modified version of the Terraform dag code with the Terraform dependencies removed.

Example

package main

import (
	"fmt"
	"time"

	"github.com/silas/dag"
)

func main() {
	g := &dag.AcyclicGraph{}

	p := "<complete>"

	g.Add(p)

	g.Add("a")
	g.Connect(dag.BasicEdge(p, "a"))

	g.Add("b")
	g.Connect(dag.BasicEdge(p, "b"))
	g.Connect(dag.BasicEdge("b", "a"))

	g.Add("c")
	g.Connect(dag.BasicEdge(p, "c"))
	g.Connect(dag.BasicEdge("c", "a"))

	if err := g.Validate(); err != nil {
		panic(err)
	}

	g.Walk(func(v dag.Vertex) (d dag.Diagnostics) {
		key := v.(string)

		fmt.Println(key)
		time.Sleep(2 * time.Second)

		return
	})
}

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func StronglyConnected

func StronglyConnected(g *Graph) [][]Vertex

StronglyConnected returns the list of strongly connected components within the Graph g. This information is primarily used by this package for cycle detection, but strongly connected components have widespread use.

func VertexName

func VertexName(raw Vertex) string

VertexName returns the name of a vertex.

Types

type AcyclicGraph

type AcyclicGraph struct {
	Graph
}

AcyclicGraph is a specialization of Graph that cannot have cycles.

func (*AcyclicGraph) Ancestors

func (g *AcyclicGraph) Ancestors(v Vertex) (Set, error)

Returns a Set that includes every Vertex yielded by walking down from the provided starting Vertex v.

func (*AcyclicGraph) Cycles

func (g *AcyclicGraph) Cycles() [][]Vertex

func (*AcyclicGraph) DepthFirstWalk

func (g *AcyclicGraph) DepthFirstWalk(start Set, f DepthWalkFunc) error

DepthFirstWalk does a depth-first walk of the graph starting from the vertices in start.

func (*AcyclicGraph) Descendents

func (g *AcyclicGraph) Descendents(v Vertex) (Set, error)

Returns a Set that includes every Vertex yielded by walking up from the provided starting Vertex v.

func (*AcyclicGraph) DirectedGraph

func (g *AcyclicGraph) DirectedGraph() Grapher

func (*AcyclicGraph) ReverseDepthFirstWalk

func (g *AcyclicGraph) ReverseDepthFirstWalk(start Set, f DepthWalkFunc) error

ReverseDepthFirstWalk does a depth-first walk _up_ the graph starting from the vertices in start.

func (*AcyclicGraph) Root

func (g *AcyclicGraph) Root() (Vertex, error)

Root returns the root of the DAG, or an error.

Complexity: O(V)

func (*AcyclicGraph) SortedDepthFirstWalk

func (g *AcyclicGraph) SortedDepthFirstWalk(start []Vertex, f DepthWalkFunc) error

SortedDepthFirstWalk does a depth-first walk of the graph starting from the vertices in start, always iterating the nodes in a consistent order.

func (*AcyclicGraph) SortedReverseDepthFirstWalk

func (g *AcyclicGraph) SortedReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error

SortedReverseDepthFirstWalk does a depth-first walk _up_ the graph starting from the vertices in start, always iterating the nodes in a consistent order.

func (*AcyclicGraph) TransitiveReduction

func (g *AcyclicGraph) TransitiveReduction()

TransitiveReduction performs the transitive reduction of graph g in place. The transitive reduction of a graph is a graph with as few edges as possible with the same reachability as the original graph. This means that if there are three nodes A => B => C, and A connects to both B and C, and B connects to C, then the transitive reduction is the same graph with only a single edge between A and B, and a single edge between B and C.

The graph must be valid for this operation to behave properly. If Validate() returns an error, the behavior is undefined and the results will likely be unexpected.

Complexity: O(V(V+E)), or asymptotically O(VE)

func (*AcyclicGraph) Validate

func (g *AcyclicGraph) Validate() error

Validate validates the DAG. A DAG is valid if it has a single root with no cycles.

func (*AcyclicGraph) Walk

func (g *AcyclicGraph) Walk(cb WalkFunc) Diagnostics

Walk walks the graph, calling your callback as each node is visited. This will walk nodes in parallel if it can. The resulting diagnostics contains problems from all graphs visited, in no particular order.

type DepthWalkFunc

type DepthWalkFunc func(Vertex, int) error

DepthWalkFunc is a walk function that also receives the current depth of the walk as an argument

type Description

type Description struct {
	Summary string
	Detail  string
}

type Diagnostic

type Diagnostic interface {
	Severity() Severity
	Description() Description
}

type Diagnostics

type Diagnostics []Diagnostic

Diagnostics is a list of diagnostics. Diagnostics is intended to be used where a Go "error" might normally be used, allowing richer information to be conveyed (more context, support for warnings).

A nil Diagnostics is a valid, empty diagnostics list, thus allowing heap allocation to be avoided in the common case where there are no diagnostics to report at all.

func (Diagnostics) Append

func (diags Diagnostics) Append(new ...interface{}) Diagnostics

Append is the main interface for constructing Diagnostics lists, taking an existing list (which may be nil) and appending the new objects to it after normalizing them to be implementations of Diagnostic.

The usual pattern for a function that natively "speaks" diagnostics is:

// Create a nil Diagnostics at the start of the function
var diags diag.Diagnostics

// At later points, build on it if errors / warnings occur:
foo, err := DoSomethingRisky()
if err != nil {
    diags = diags.Append(err)
}

// Eventually return the result and diagnostics in place of error
return result, diags

Append accepts a variety of different diagnostic-like types, including native Go errors and HCL diagnostics. It also knows how to unwrap a multierror.Error into separate error diagnostics. It can be passed another Diagnostics to concatenate the two lists. If given something it cannot handle, this function will panic.

func (Diagnostics) Err

func (diags Diagnostics) Err() error

Err flattens a diagnostics list into a single Go error, or to nil if the diagnostics list does not include any error-level diagnostics.

This can be used to smuggle diagnostics through an API that deals in native errors, but unfortunately it will lose naked warnings (warnings that aren't accompanied by at least one error) since such APIs have no mechanism through which to report these.

return result, diags.Error()

func (Diagnostics) ErrWithWarnings

func (diags Diagnostics) ErrWithWarnings() error

ErrWithWarnings is similar to Err except that it will also return a non-nil error if the receiver contains only warnings.

In the warnings-only situation, the result is guaranteed to be of dynamic type NonFatalError, allowing diagnostics-aware callers to type-assert and unwrap it, treating it as non-fatal.

This should be used only in contexts where the caller is able to recognize and handle NonFatalError. For normal callers that expect a lack of errors to be signaled by nil, use just Diagnostics.Err.

func (Diagnostics) HasErrors

func (diags Diagnostics) HasErrors() bool

HasErrors returns true if any of the diagnostics in the list have a severity of Error.

func (Diagnostics) NonFatalErr

func (diags Diagnostics) NonFatalErr() error

NonFatalErr is similar to Err except that it always returns either nil (if there are no diagnostics at all) or NonFatalError.

This allows diagnostics to be returned over an error return channel while being explicit that the diagnostics should not halt processing.

This should be used only in contexts where the caller is able to recognize and handle NonFatalError. For normal callers that expect a lack of errors to be signaled by nil, use just Diagnostics.Err.

func (Diagnostics) Sort

func (diags Diagnostics) Sort()

Sort applies an ordering to the diagnostics in the receiver in-place.

The ordering is: warnings before errors, sourceless before sourced, short source paths before long source paths, and then ordering by position within each file.

Diagnostics that do not differ by any of these sortable characteristics will remain in the same relative order after this method returns.

type DotNode

type DotNode struct {
	Name  string
	Attrs map[string]string
}

DotNode provides a structure for Vertices to return in order to specify their dot format.

type DotOpts

type DotOpts struct {
	// Allows some nodes to decide to only show themselves when the user has
	// requested the "verbose" graph.
	Verbose bool

	// Highlight Cycles
	DrawCycles bool

	// How many levels to expand modules as we draw
	MaxDepth int
	// contains filtered or unexported fields
}

DotOpts are the options for generating a dot formatted Graph.

type Edge

type Edge interface {
	Source() Vertex
	Target() Vertex

	Hashable
}

Edge represents an edge in the graph, with a source and target vertex.

func BasicEdge

func BasicEdge(source, target Vertex) Edge

BasicEdge returns an Edge implementation that simply tracks the source and target given as-is.

type Graph

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

Graph is used to represent a dependency graph.

func (*Graph) Add

func (g *Graph) Add(v Vertex) Vertex

Add adds a vertex to the graph. This is safe to call multiple time with the same Vertex.

func (*Graph) Connect

func (g *Graph) Connect(edge Edge)

Connect adds an edge with the given source and target. This is safe to call multiple times with the same value. Note that the same value is verified through pointer equality of the vertices, not through the value of the edge itself.

func (*Graph) DirectedGraph

func (g *Graph) DirectedGraph() Grapher

func (*Graph) Dot

func (g *Graph) Dot(opts *DotOpts) []byte

Dot returns a dot-formatted representation of the Graph.

func (*Graph) DownEdges

func (g *Graph) DownEdges(v Vertex) Set

DownEdges returns the vertices connected from the inward edges to Vertex v.

func (*Graph) Edges

func (g *Graph) Edges() []Edge

Edges returns the list of all the edges in the graph.

func (*Graph) EdgesFrom

func (g *Graph) EdgesFrom(v Vertex) []Edge

EdgesFrom returns the list of edges from the given source.

func (*Graph) EdgesTo

func (g *Graph) EdgesTo(v Vertex) []Edge

EdgesTo returns the list of edges to the given target.

func (*Graph) HasEdge

func (g *Graph) HasEdge(e Edge) bool

HasEdge checks if the given Edge is present in the graph.

func (*Graph) HasVertex

func (g *Graph) HasVertex(v Vertex) bool

HasVertex checks if the given Vertex is present in the graph.

func (*Graph) Remove

func (g *Graph) Remove(v Vertex) Vertex

Remove removes a vertex from the graph. This will also remove any edges with this vertex as a source or target.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(edge Edge)

RemoveEdge removes an edge from the graph.

func (*Graph) Replace

func (g *Graph) Replace(original, replacement Vertex) bool

Replace replaces the original Vertex with replacement. If the original does not exist within the graph, then false is returned. Otherwise, true is returned.

func (*Graph) String

func (g *Graph) String() string

String outputs some human-friendly output for the graph structure.

func (*Graph) StringWithNodeTypes

func (g *Graph) StringWithNodeTypes() string

String outputs some human-friendly output for the graph structure.

func (*Graph) UpEdges

func (g *Graph) UpEdges(v Vertex) Set

UpEdges returns the vertices connected to the outward edges from the source Vertex v.

func (*Graph) Vertices

func (g *Graph) Vertices() []Vertex

Vertices returns the list of all the vertices in the graph.

type GraphNodeDotter

type GraphNodeDotter interface {
	// Dot is called to return the dot formatting for the node.
	// The first parameter is the title of the node.
	// The second parameter includes user-specified options that affect the dot
	// graph. See GraphDotOpts below for details.
	DotNode(string, *DotOpts) *DotNode
}

GraphNodeDotter can be implemented by a node to cause it to be included in the dot graph. The Dot method will be called which is expected to return a representation of this node.

type Grapher

type Grapher interface {
	DirectedGraph() Grapher
}

A Grapher is any type that returns a Grapher, mainly used to identify dag.Graph and dag.AcyclicGraph. In the case of Graph and AcyclicGraph, they return themselves.

type Hashable

type Hashable interface {
	Hashcode() interface{}
}

Hashable is the interface used by set to get the hash code of a value. If this isn't given, then the value of the item being added to the set itself is used as the comparison value.

type NamedVertex

type NamedVertex interface {
	Vertex
	Name() string
}

NamedVertex is an optional interface that can be implemented by Vertex to give it a human-friendly name that is used for outputting the graph.

type NonFatalError

type NonFatalError struct {
	Diagnostics
}

NonFatalError is a special error type, returned by Diagnostics.ErrWithWarnings and Diagnostics.NonFatalErr, that indicates that the wrapped diagnostics should be treated as non-fatal. Callers can conditionally type-assert an error to this type in order to detect the non-fatal scenario and handle it in a different way.

func (NonFatalError) Error

func (woe NonFatalError) Error() string

type Set

type Set map[interface{}]interface{}

Set is a set data structure.

func (Set) Add

func (s Set) Add(v interface{})

Add adds an item to the set

func (Set) Copy

func (s Set) Copy() Set

Copy returns a shallow copy of the set.

func (Set) Delete

func (s Set) Delete(v interface{})

Delete removes an item from the set.

func (Set) Difference

func (s Set) Difference(other Set) Set

Difference returns a set with the elements that s has but other doesn't.

func (Set) Filter

func (s Set) Filter(cb func(interface{}) bool) Set

Filter returns a set that contains the elements from the receiver where the given callback returns true.

func (Set) Include

func (s Set) Include(v interface{}) bool

Include returns true/false of whether a value is in the set.

func (Set) Intersection

func (s Set) Intersection(other Set) Set

Intersection computes the set intersection with other.

func (Set) Len

func (s Set) Len() int

Len is the number of items in the set.

func (Set) List

func (s Set) List() []interface{}

List returns the list of set elements.

type Severity

type Severity rune
const (
	Error   Severity = 'E'
	Warning Severity = 'W'
)

func (Severity) String

func (i Severity) String() string

type Subgrapher

type Subgrapher interface {
	Subgraph() Grapher
}

Subgrapher allows a Vertex to be a Graph itself, by returning a Grapher.

type Vertex

type Vertex interface{}

Vertex of the graph.

func AsVertexList

func AsVertexList(s Set) []Vertex

simple convenience helper for converting a dag.Set to a []Vertex

type WalkFunc

type WalkFunc func(Vertex) Diagnostics

WalkFunc is the callback used for walking the graph.

type Walker

type Walker struct {
	// Callback is what is called for each vertex
	Callback WalkFunc

	// Reverse, if true, causes the source of an edge to depend on a target.
	// When false (default), the target depends on the source.
	Reverse bool
	// contains filtered or unexported fields
}

Walker is used to walk every vertex of a graph in parallel.

A vertex will only be walked when the dependencies of that vertex have been walked. If two vertices can be walked at the same time, they will be.

Update can be called to update the graph. This can be called even during a walk, changing vertices/edges mid-walk. This should be done carefully. If a vertex is removed but has already been executed, the result of that execution (any error) is still returned by Wait. Changing or re-adding a vertex that has already executed has no effect. Changing edges of a vertex that has already executed has no effect.

Non-parallelism can be enforced by introducing a lock in your callback function. However, the goroutine overhead of a walk will remain. Walker will create V*2 goroutines (one for each vertex, and dependency waiter for each vertex). In general this should be of no concern unless there are a huge number of vertices.

The walk is depth first by default. This can be changed with the Reverse option.

A single walker is only valid for one graph walk. After the walk is complete you must construct a new walker to walk again. State for the walk is never deleted in case vertices or edges are changed.

func (*Walker) Update

func (w *Walker) Update(g *AcyclicGraph)

Update updates the currently executing walk with the given graph. This will perform a diff of the vertices and edges and update the walker. Already completed vertices remain completed (including any errors during their execution).

This returns immediately once the walker is updated; it does not wait for completion of the walk.

Multiple Updates can be called in parallel. Update can be called at any time during a walk.

func (*Walker) Wait

func (w *Walker) Wait() Diagnostics

Wait waits for the completion of the walk and returns diagnostics describing any problems that arose. Update should be called to populate the walk with vertices and edges prior to calling this.

Wait will return as soon as all currently known vertices are complete. If you plan on calling Update with more vertices in the future, you should not call Wait until after this is done.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL