Petgraph: Adding a new node invalidates references to node weights

1

I was finally able to create a small reproduction of an infrequent error that's been plaguing a project of mine.

I'm trying to build a universal game-playing program. Like most such programs, it works by building a search tree over possible game states.

In this pared down example, I'm simply constructing every possible state of Tic Tac Toe:

Lines 63-75 are the crucial lines. From any given state, it will play all possible next moves and add those to the state tree.

state and state_clone should always refer to the same thing, but they don't. Something about adding new nodes to the Graph changes the referent of state. And it changes it to a strange, invalid state.

Couple of questions: why does adding a new node affect an existing node like this? Where is that strange all-Cross state coming from?

2

It is coming from undefined behavior. You're modifying a data structure and expecting existing references to things inside of it to remain valid. That is not the case (which is why you can't do what you're trying to do without unsafe). In particular, the Vec inside of Graph is reallocating so you're pointing into freed memory.

3 Likes
3

When you put it that way, it seems so obvious. Thanks!