Безопасные нетривиальные зависимости данных/пользовательские ссылки?

Question

Одной из центральных особенностей Rust является постоянная безопасность ссылок, которая достигается за счет механики владения и явного времени жизни. Возможно ли реализовать «пользовательские» ссылки, которые выиграют от того же?

Рассмотрим следующий пример. У нас есть объект, представляющий граф. Предположим, что мы можем пересечь график, ссылаясь на его ребра, однако эти ссылки реализуются как пользовательские индексы, а не указывают на некоторую память. Такой индекс может быть просто смещением в массив (или три), но он также может быть структурой, которая объединяет некоторые флаги и т. Д.

Помимо перемещения по графику, мы также можем изменить его, что означает, что ссылки на его внутреннее состояние (ребра) становятся недействительными. В идеале мы хотели бы, чтобы компилятор поймал любую из этих недопустимых ссылок. Можем ли мы сделать это в Rust? Например:

// 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() 

P.S. Извините за неинформативные названия, я не был уверен, как фраза его ...

Answer 1

Вы можете добавить время жизни в вашей Edge структуры, и заимствовать Graph в get_random_edge метода:

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) 
    } 
} 

Это будет дают следующие ошибки:

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 

И

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 

Если вы не хотите хранить ссылку на Graph на краю, но только индекс, вы можете просто заменить &'a mut Graph на PhantomData<&'a mut Graph>, который не занимает память, но имеет ту же семантику.

Answer 2

Да

---

Вполне возможно использовать право собственности и заимствовать проверки строить собственные проверки безопасности, и это на самом деле очень захватывающая область исследования, которая открывается нам.

Я хотел бы начать с существующими интересными вещами:

• Sessions Types около кодирующих автоматов в системе типов:

  • «Состояние» кодируются как тип
  • «Переход» кодируется как метод, потребляющий одно значение и создающий другой, возможно, другой тип
  • В результате: (1) переходы являются проверкой d во время выполнения и (2), что невозможно использовать старое состояние

• Есть уловки, чтобы использовать заимствование подделать гарантированный допустимый индекс для конкретной коллекции (связанные с брендингом):

  • В индекс не заимствует сбор, гарантируя сбор не может быть изменен
  • индекс подделан с инвариантной жизни, которая связывает его этого экземпляра коллекции, и никакого другого
  • В результате: индекс может быть использован только с этой коллекцией, и без проверки границ

---

Давайте перейдем к вашим примерам:

// 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! 

Это действительно тривиальное.

В Rust вы можете определить метод взять на себя ответственность своего приемника:

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

Как только значение потребляется, она не может быть использована больше, и, следовательно, вызов next является недействительным.

Я полагаю, что вы хотели бы Edge сохранить ссылку на график, чтобы предотвратить график от изменений, пока у вас есть выдающийся край:

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

будет делать трюк.

---

Перемещение по:

// 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() 

Это не представляется возможным, так как есть.

Чтобы обеспечить соблюдение порядка, значения должны быть связаны друг с другом, а здесь edge1 и edge2 - нет.

Простое решение потребовать, чтобы edge1 действовать в качестве обязательного прокси для графа:

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

Затем, мы реализуем поглотитель, чтобы получить доступ к графику временно:

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

И использует этот результат (так называемый graph2 для удобства), чтобы получить edge2.

Это создает цепь обязательств:

• Никто не может коснуться до edge1 умирает
• Никто не может коснуться edge1 до graph2 умирает
• Никто не может коснуться graph2 до edge2 умирает

который обеспечивает, чтобы объекты были выпущены в правильном порядке.

Во время компиляции.

\ о/

---

безопасность Примечание: Важное событие в ранних сроках после Rust релиз был LeakPocalypse (scoped_thread быть признаны несостоятельными), что привело Gankro (который написал и пастух std::collections) написать Pre-pooping Your Pants with Rust который я призываю вас прочитать. Короче говоря, вы НИКОГДА не должны полагаться на деструктор, выполняемый для безопасности, потому что нет никакой гарантии, что он (объект может быть просочился, а затем поток раскрутится от паники). Pre-Pooping Your Pants - это стратегия, предложенная Gankro, чтобы обойти это: поставить элемент в действительное и безопасное (если это семантически неправильно) состояние, сделать ваши вещи, восстановить настоящую семантику при уничтожении и использовать то, что используется Drain итератор.