Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

AdjacencyMap may cause panic #102

Open
liuxiaomeiG opened this issue Apr 20, 2023 · 3 comments · May be fixed by #157
Open

AdjacencyMap may cause panic #102

liuxiaomeiG opened this issue Apr 20, 2023 · 3 comments · May be fixed by #157
Labels
bug Something isn't working

Comments

@liuxiaomeiG
Copy link

Concurrent calls to AddVertex, AddEdge, and AdjacencyMap redundantly panic.

panic: assignment to entry in nil map

goroutine 1996 [running]:
github.com/dominikbraun/graph.(*undirected[...]).AdjacencyMap(0xc0009542c0?)
	github.com/dominikbraun/[email protected]/undirected.go:167 +0x225

image

ListVertices and ListEdges directly occur AddVertex and AddEdge will cause this problem
@davidovich
Copy link

We have experienced this also in a non concurrent environment. PredecessorMap() is guarded against nil access, I wonder if it was intended to leave it out in AdjacencyMap(). If not, would you accept a PR to add an initialization if the edge.Target is not found ?

@dominikbraun dominikbraun added the bug Something isn't working label Oct 13, 2023
@dominikbraun
Copy link
Owner

@davidovich Yes. AdjacencyMap should behave exactly as PredecessorMap since these functions do the same thing but complement each other.

davidovich added a commit to davidovich/graph that referenced this issue Oct 13, 2023
@davidovich
Fix potential panic on AdjacencyMap
391493f 
Because the store could theoretically be updated without the use of the
main `AddVertex` and `AddEdge` APIs (which does some input validation),
calculating the `AdjencyMap` could provoke an "assignment to entry in
nil map" panic if the store reported edges that were between unknown
vertices.

Since the edges are always between known vertices, it is an error to try
and match a missing source vertex from the vertex set. If that happens,
it is a data desynchronization error that we report to the user.

In order to test this pathological case, we needed to modify the test to
use the store directly because the "front-facing" API would not allow us
to add Edges on missing vertex.

fixes dominikbraun#102

Signed-off-by: davidovich <[email protected]>
@davidovich davidovich linked a pull request Oct 13, 2023 that will close this issue
Open
@davidovich
Copy link

While investigating this issue, it appeared to me that the code is correct on assuming the presence of a vertex, hence it would be, IMHO, a bad fix to just initialize the map on an un-existing source vertex because that would create a degenerate edge.

In our implementation of the store interface, we hit a panic because the store was returning edges with vertices that did not exist. So I went and opened a PR for reporting that error instead of panicking.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix potential panic on AdjacencyMap davidovich/graph
3 participants
@davidovich @liuxiaomeiG @dominikbraun