Occasional panic in Graph.Toposort()

[smyrman]

This isn't the most informative bug report; I am sorry about that.

We have discovered that we sometimes see an occasional panic occur at this exact code line:

go-toposort/toposort.go

Line 79 in 9be86db

ms[i-1] = m

We have seen it about 2 times in 6 months on our production system (although it may have occurred more often without us explicitly noticing it). Unfortunately we don't currently have a reproduction case.

I suppose a good start for me, would be to ask if there are any known cases where this line is expected to panic (e.g. on invalid input of some type).

[smyrman]

We are still seeing this issue. I belive the reason why we don't see it consistently is because we are looping through a map when adding nodes and edges, which means we add the nodes and edges in an arbitrary order.

Somewhat simplified, our code looks something like this:

	// src is of type map[string]Object
	// Object has an ID, and a list of dependencies (Deps).
	// Each entry in Deps is a struct with field  ObjectID,
	// referring to an Object instance which might or might
        // not be in the graph.
	graph := toposort.NewGraph(len(src))
	for _, obj := range src {
		graph.AddNode(obj.ID)
	}

	for i, obj := range src {
		for j, dep := range obj.Deps {
			graph.AddEdge(obj.ID, dep.ObjectID)
		}
	}

	// check for circular dependencies using toposort
	ids, ok := graph.Toposort()
	if !ok {
		return nil
	}

[n-g]

Maybe related:
Adding an edge twice does not return false but leads to a panic when sorting the graph.

graph := toposort.NewGraph(2)

graph.AddNode("a")
graph.AddNode("b")

graph.AddEdge("a", "b")
graph.AddEdge("a", "b")

graph.Toposort()

panic: runtime error: index out of range [1] with length 1