avl/savefile

Stack-overflow for recursive data-structures

avl opened this issue · 1 comments

avl commented

Savefile does not presently support recursive data-structures.

To be precise, the problem is with the schema-function. The schema-function tries to provide a simple tree which describes the data format. However, this fails if the data is recursive in nature.

Consider this data structure:

struct TreeNode(u32, Vec<TreeNode>);

The schema for TreeNode is basically a tuple of (u32,[TreeNode]). But savefile will try to evaluate the schema down to primitives, and will thus evaluate the schema of TreeNode again, yielding (u32,[(u32,[TreeNode])]), then (u32,[(u32,[(u32,[TreeNode])])]) etc in infinity.

Savefile is previously documented as not supporting cyclic data structures. But as now discovered, any recursive data structure, even without actual cycles, causes problems.

I can see 3 possible ways forward:

1: Just document that recursive data structures are not supported. Possibly add some sort of recursion-limit to detect the problem.

2: Add support for recursive data structures.

3: Possibly add full support for serializing/deserializing arbitrary graphs, including graphs with cycles

avl commented

Option 2) above was chosen. Savefile 0.17 will support recursive data structures.