Я заинтересован в поиске или реализации структуры данных Rust, которая обеспечивает способ нулевой стоимости для запоминания одного вычисления с произвольным типом вывода T. В частности, я бы хотел универсальный тип Cache<T>, чьи внутренние данные занимают не больше места, чем Option<T>, со следующим базовым API:
impl<T> Cache<T> {
/// Return a new Cache with no value stored in it yet.
pub fn new() -> Self {
// ...
}
/// If the cache has a value stored in it, return a reference to the
/// stored value. Otherwise, compute `f()`, store its output
/// in the cache, and then return a reference to the stored value.
pub fn call<F: FnOnce() -> T>(&self, f: F) -> &T {
// ...
}
}
Цель здесь - иметь возможность совместно использовать несколько неизменных ссылок на Cache в одном потоке, причем любой держатель такой ссылки может получить доступ к значению (запуск вычисления, если это происходит в первый раз). Поскольку нам нужно только иметь возможность совместно использовать Cache в одном потоке, необязательно, чтобы он был Sync.
Вот способ безопасно реализовать API (или, по крайней мере, я думаю, что он безопасен), используя unsafe под капотом:
use std::cell::UnsafeCell;
pub struct Cache<T> {
value: UnsafeCell<Option<T>>
}
impl<T> Cache<T> {
pub fn new() -> Self {
Cache { value: UnsafeCell::new(None) }
}
pub fn call<F: FnOnce() -> T>(&self, f: F) -> &T {
let ptr = self.value.get();
unsafe {
if (*ptr).is_none() {
let t = f();
// Since `f` potentially could have invoked `call` on this
// same cache, to be safe we must check again that *ptr
// is still None, before setting the value.
if (*ptr).is_none() {
*ptr = Some(t);
}
}
(*ptr).as_ref().unwrap()
}
}
}
Возможно ли реализовать такой тип в безопасном Rust (т.е. не писать собственный код unsafe, а только косвенно полагаться на код unsafe в стандартной библиотеке)?
Очевидно, что метод call требует мутации self, что означает, что Cache должен использовать некоторую форму внутренней изменчивости. Тем не менее, кажется, что это невозможно сделать с Cell, потому что Cell не предоставляет способа получить ссылку на вложенное значение, как того требует требуемый API call выше. И это по уважительной причине, поскольку для Cell было бы неправильно предоставлять такую ссылку, потому что не было бы никакого способа гарантировать, что указанное значение не будет изменено в течение времени жизни ссылки. С другой стороны, для типа Cache после однократного вызова call API, приведенный выше, не предоставляет никакого способа для повторения мутирования сохраненного значения, поэтому для него безопасно выдать ссылку с время жизни, которое может быть таким же, как у самого Cache.
Если Cell не может работать, мне любопытно, может ли стандартная библиотека Rust предоставить некоторые другие безопасные строительные блоки для внутренней изменчивости, которые можно использовать для реализации этого Cache.
Ни RefCell, ни Mutex не достигают цели здесь:
- они не имеют нулевой стоимости: они включают в себя хранение большего количества данных, чем у
Option<T>, и добавляют ненужные проверки во время выполнения.
- кажется, что они не дают никакого способа вернуть реальную ссылку с желаемым временем жизни - вместо этого мы можем вернуть только
Ref или MutexGuard, что не одно и то же.
Использование только Option не обеспечит такую же функциональность: если мы поделимся неизменными ссылками на Cache, любой держатель такой ссылки может вызвать call и получить желаемое значение (и изменить Cache в процессе, чтобы будущие вызовы извлекли то же самое значение); тогда как, разделяя неизменные ссылки на Option, было бы невозможно изменить Option, поэтому он не мог работать.