Sunday, April 06, 2014

A very rough few thoughts on initialising data structures in Rust

This is not a well thought out blog post. It ought to be a tweet, but it is too long.

Thoughts (in kind of random order):
  • Rust has an ownership model based on hierarchies.
  • It is easy to support tree-based data structures this way.
  • Structures with cycles are much more annoying.
  • The real pain is in initialisation.
  • You can have a data structure with cycles using ref-counting or borrowed references as long as you 'delete' the whole data structure at once.
  • Rust helps you do this with its type system.
  • BUT there is no way to initialise such a data structure because of the way `mut` works. Specifically the requirement that `mut` variables are unique and have move/borrow semantics.
  • Therefore you need unsafe blocks, which is a pain.
  • Since it seems that you ought to be able to verify safe initialisation (I'm not sure how though).
  • I think this is an area of the language which has not caused much pain because compilers (especially the frontend) and browsers are both very 'tree-heavy' programs. Long term we should find a solution to this, but it is certainly something that can be put off till post-1.0 (since it has an unsafe solution and I can' imagine a safe solution not being backwards-compatible).
  • Kind of related - when using a data structure where all components have the same lifetime (i.e., the whole structure must be destroyed at once) you end up writing a huge number of really un-interesting lifetime parameters on functions and data which basically just get passed around. I would love to have a shorthand here - perhaps modules could have lifetime parameters? Not sure if that would help that much. More thought required in any case...


payload said...

What do you think about using another indirection by using a map and integers as IDs and keys to the values which link graphlike to one another? and never making direct references to one another

Nick Cameron. said...

@payload - I think it is one implementation strategy with some strengths and weaknesses. In a way I think it is orthogonal to my thoughts about a more standard graph implementation. I think that up-front you would have a bunch of design constraints that led you to either a direct or indirect graph, and you should be able to go with the appropriate design. If the appropriate design is indirect, fine. If the appropriate design is direct, then the language should not force you into using the indirect design.

kjx said...

Is it to cynical to ask if this is one of the differences between external uniqueness and ownership?

(not that I'll remember to look here for the answer)

Unknown said...

Excellent info ............
what is data structure and its types