Safe nontrivial data dependencies / user links?

Question

One of the central features of Rust is the constant security of links, which is achieved through ownership mechanics and an explicit lifetime. Is it possible to implement “custom” links that benefit from the same?

Consider the following example. We have an object representing a graph. Suppose we can cross a graph by referencing its edges, however, these links are implemented as user indices, rather than pointing to some memory. Such an index can simply be an offset into an array (or three), but it can also be a structure that combines some flags, etc.

In addition to moving the graph, we can also change it, which means that references to its internal state (edges) become invalid. Ideally, we would like the compiler to catch any of these invalid links. Can we do this in Rust? For instance:.

// get a reference to an edge let edge = graph.get_random_edge() // the next statement yields the ownership of the edge reference // back to the graph, which can invalidate it edge.split() edge.next() // this will be a compile-time error as the edge is gone! // another example let edge1 = graph.get_random_edge() let edge2 = graph.get_random_edge() // this will be a compile-time error because the potentially invalid // edge2 reference is still owned by the code and has not been // yielded to the graph edge1.split() 

PS Sorry for the uninformative title, I was not sure how to express it ...

Answer 1

Yes

---

It is completely possible to use ownership and borrow funds to create your own security checks, and this is indeed a very interesting area of ​​research that is open to us.

I would like to start with existing interesting things:

• Session types refer to coding state machines in a type system:

  • "Status" is encoded as type
  • A "transition" is encoded as a method that consumes one value and creates another, possibly another type
  • As a result: (1) transitions are checked at runtime and (2) it is not possible to use the old state

• There are tricks to using borrowing to create a guaranteed valid index for a specific collection (related to branding):

  • The index borrows the fee, ensuring that the fee cannot be changed.
  • The index is faked with an invariable lifetime that links it to this instance of the collection, and another
  • As a result: the index can only be used with this collection and can be checked without restrictions

---

Back to your examples:

 // get a reference to an edge let edge = graph.get_random_edge() // the next statement yields the ownership of the edge reference // back to the graph, which can invalidate it edge.split() edge.next() // this will be a compile-time error as the edge is gone! 

This is actually trivial.

In Rust, you can define how to capture your recipient:

 impl Edge { fn split(self) { ... } // ^~~~ Look, no "&" } 

Once the value has been consumed, it can no longer be used, so the next call is invalid.

I assume that you would like Edge maintain a link to the graph in order to prevent the graph from changing while you have an outstanding edge:

 struct Edge<'a> { graph: &'a Graph, // nobody modifies the graph while I live! } 

will do the trick.

---

Moving:

 // another example let edge1 = graph.get_random_edge() let edge2 = graph.get_random_edge() // this will be a compile-time error because the potentially invalid // edge2 reference is still owned by the code and has not been // yielded to the graph edge1.split() 

It is impossible as it is.

To ensure that the order is maintained, the values ​​must be related to each other, but here edge1 and edge2 are not.

A simple solution is to require edge1 act as the required proxy for the graph:

 struct Edge<'a> { graph: &'a mut Graph, // MY PRECIOUS! // You'll only get that graph over my dead body! } 

Then we implement getter to temporarily access the chart:

 impl<'a> Edge<'a> { fn get_graph<'me>(&'me mut edge) -> &'me mut Graph; } 

And uses this result (named graph2 for convenience) to get edge2 .

This creates a chain of obligations:

• No one can touch graph until edge1 dies
• No one can touch edge1 until graph2 dies
• No one can touch graph2 until edge2 dies

which ensures that objects are released in the correct order.

At compile time.

\ about /

---

Safety note. An important event at the beginning of the release of Rust was LeakPocalypse ( scoped_thread , which was declared bankrupt), which led Gankro (who wrote and pasted std::collections ) to write Pre-pooping Your Pants with Rust , which I urge you to read. In short, you should NEVER rely on a destructor executed to ensure security, because there is no guarantee that it (the object may be leaked, and then the thread will relax from panic). Pre-Pooping Your Pants is a strategy proposed by Gankro to get around this: put the element in a valid and safe (if it is semantically incorrect) state, do your stuff, restore real semantics when destroyed, and this is what the Drain iterator uses .

Answer 2

You can add life to your Edge structure and take Graph in the get_random_edge method:

 struct Graph; impl Graph { fn get_random_edge<'a>(&'a self) -> Edge<'a> { Edge(self) } fn get_random_edge_mut<'a>(&'a mut self) -> MutEdge<'a> { MutEdge(self) } } struct MutEdge<'a>(&'a mut Graph); impl<'a> MutEdge<'a> { fn split(self) {} fn next(&'a mut self) -> MutEdge<'a> { MutEdge(self.0) } } struct Edge<'a>(&'a Graph); impl<'a> Edge<'a> { fn split(self) {} fn next(&'a self) -> Edge<'a> { Edge(self.0) } } 

This will result in the following errors:

 37 | edge.split(); | ---- value moved here 38 | edge.next(); // this will be a compile-time error as the edge is gone! | ^^^^ value used here after move 

and

 error[E0499]: cannot borrow `graph` as mutable more than once at a time --> <anon>:43:17 | 42 | let edge1 = graph.get_random_edge_mut(); | ----- first mutable borrow occurs here 43 | let edge2 = graph.get_random_edge_mut(); | ^^^^^ second mutable borrow occurs here 

If you don’t want to store a link to Graph in the edge, but only an index, you can simply replace &'a mut Graph with PhantomData<&'a mut Graph> , which does not take memory but has the same semantics.