Могу ли я доказать монотонность ассигнований с помощью Rust Borrow Checker
У меня есть следующий код, который не компилируется:
// TODO: Return Result, remove `.expect`s
fn to_blender_subfile<'a>(
filepath: &str,
transform: Transform,
visited_file_cache: &'a mut HashMap<&'a str, Vec<Command>>,
blender: &mut Blender,
) {
// TODO: Support colors and backface culling
let commands = visited_file_cache.get(filepath).unwrap();
// "unwrap" is enforced by the wrapper function
for command in commands.iter() {
if let Command::Subfile { filepath, .. } = command {
if !visited_file_cache.contains_key(filepath.as_str()) {
let mut file = std::fs::File::open(filepath).expect("Failed to open file");
let mut file_contents = String::new();
let contents_len = file
.read_to_string(&mut file_contents)
.expect("Failed to read file into buffer");
assert_eq!(contents_len, file_contents.len()); // TODO: Check this
// "parse_file" is defined elsewhere
let commands = parse_file(&file_contents);
if let Some(_) = visited_file_cache.insert(filepath.as_str(), commands) {
std::unreachable!();
}
}
}
}
// ... rest of function
}
Ошибка, которую я получаю от rustc:
cannot borrow `*visited_file_cache` as mutable because it is also borrowed as immutable
имея в виду тот факт, что я делаю visited_file_cache.insert(filepath.as_str(), commands) и let commands = visited_file_cache.get(filepath).unwrap();, утверждая visited_file_cache: &'a mut HashMap<&'a str, Vec<Command>>.
Насколько я понимаю, что происходит, по крайней мере, на высоком уровне, это то, что программа проверки заимствований защищает меня от мутаций visited_file_cache, а также ссылается на свои значения для своих ключей, поскольку в целом его ключи могут пережить свои значения, что может привести к висячим указателям .
Это все хорошо, однако по природе кода, если пара ключ-значение была вставлена в visited_file_cache, ее нельзя удалить (т. е. она живет, по крайней мере, до тех пор, пока сама хэш-карта). Я понимаю, что компилятор не может использовать эту информацию, поэтому и жалуется, но есть ли способ сообщить компилятору, что регион монотонно растет? Затем я мог бы сообщить компилятору, что visited_file_cache поддерживается монотонным распределителем, а его метод insert неразрушающим, тем самым избавляясь от вышеуказанной ошибки.
Может ли компилятор понимать такие структуры или в стандартной библиотеке есть предопределенные структуры, которые обеспечивают описанное выше поведение при использовании unsafe?
Я знаю, что могу тривиально обойти эту проблему, скопировав строки и сделав ключи принадлежащими visited_file_cache, и я почти уверен, что мог бы также использовать подсчет ссылок. Однако я не думаю, что инфраструктура для любого из этих двух решений необходима для моего варианта использования.
Н.Б. Я новичок в Rust (еще не просматривал Rust Book, хотя и просматривал Rustonomicon), но у меня есть опыт работы с C и Haskell.
Если подумать, то, что я упомянул, является проблемой, но это не заставит ваш код работать. Нельзя insert, пока существует выдающаяся ссылка на карту. Компилятор спасает вас от аннулирования вашего commands. Я не думаю, что ваш «монотонный распределитель» что-то исправит; Я не уверен в текущей реализации стандарта HashMap, но считаю, что вставка может вызвать перераспределение и перемещение существующих ключей/значений.
@kmdreko Почему бы и нет? С моей версией монотонной хэш-карты insert не вызовет перераспределение. insert будет «неразрушающим», как я говорю в своем вопросе. Как только вы вставите пару ключ-значение, эта пара не изменится в течение всего времени существования прилагаемой хеш-карты.
@kmdreko Практически говоря, память, поддерживающая хеш-карту, не обязательно должна быть смежной между парами (или каждым компонентом пары). Поэтому такой распределитель можно реализовать как развернутый связанный список.
Текущая реализация хеш-таблицы Rusts основана на hashbrown, который хранит всю хеш-таблицу в одном блоке памяти. Если количество вставок превышает размер этого блока, необходимо будет переместить существующие пары в новый блок большего размера, нарушая ссылки.
@user1937198 user1937198 Я это понимаю, поэтому у меня вопрос, как обойти это с помощью монотонного распределителя, как описано выше...
@WilliamRyman Не в стандарте. Вам понадобится что-то совершенно отличное от хэш-карты библиотеки std. Потому что проблема не в распределителе, а в том, как std::collections::HashMap использует распределитель.
Но даже если вы это исправите, у вас возникнут проблемы со сроком службы путей к файлам в качестве ключей. Для этого вам, вероятно, придется переключиться на использование собственного String. Самый простой способ решить эту проблему — это, вероятно, создать новую хэш-карту дополнений, а затем объединить ее с существующей картой.
@user1937198 user1937198 Неужели нет лучшего способа сделать это? То, что я хочу, кажется довольно простым. Я удивлен, что для этого нет готового решения.
@WilliamRyman Выполнение того, что вы предлагаете, включает в себя относительно сложный API, который на самом деле подходит только для одной цели (создание коллекций), где стандартная хеш-карта оптимизирована для простоты в обычном случае (перемещение элементов внутрь и наружу, без сохранения ссылок). Другим дешевым выходом было бы утверждать, что Commands Vec является неизменяемым, и помещать его в Rc. Позволяет вам освободить заимствование записи хеш-таблицы перед циклом.
Если вы хотите просто удалить подсчет ссылок, есть elsa::FrozenMap. Вместо связанного списка он требует, чтобы каждый элемент был указателем (например, Box), на который вы получаете только ссылку на его содержимое.
@drewtato Спасибо, это почти именно то, что я искал с точки зрения API.
@user1937198 user1937198 Я не понимаю, насколько сложным может быть API, по сути он точно такой же, как код, который у меня есть выше, за исключением того, что он будет просто работать... Кроме того, несмотря на то, что я предлагаю «подходить ровно для одной вещи», эта штука является обычным явлением и становится все более распространенным. Например. посмотрите на игровую индустрию и распределителей арен.
Распределители арены отличаются тем, что они являются распределителями. Поместите распределитель арены за хеш-картой хеш-коричневого цвета, и это не решит проблему, потому что пары все равно будут перемещены в новый смежный блок. Единственный способ «решить» эту проблему в распределителе — разрешить ему гарантированное расширение существующих блоков. То, что, насколько я знаю, на практике невозможно. (Распределитель арены решает эту проблему только в том случае, если вы используете его только для этой одной цели и предварительно выделяете максимально возможный размер, если вы можете согласиться с этим, просто используйте ящик хэш-карты фиксированной емкости)
Гарантии, которые вы хотите, должны быть реализованы в хэш-карте с поддержкой несмежного распределения, что значительно усложняет запросы, прежде чем вы даже позволите дизайну безопасно обрабатывать сбои в случае попытки использовать один и тот же сегмент дважды, потому что они В системе типов ржавчины нет способа доказать, что два значения не равны.
@user1937198 user1937198 Я не разбираюсь в хеш-картах hashbrown, но я определенно понимаю, как непрерывность может повлиять на алгоритм. Однако HashMap можно просто параметризовать типом распределения, а разработчик может просто статически отправлять тип (я не совсем уверен, как это сделать в Rust, но я почти уверен, что это будет выглядеть как HashMap<K, V, AllocationType::XX>) и реализовать разные алгоритмы для разных типов распределения. Таким образом, вам не придется платить за потенциально менее эффективный алгоритм, если вы его не используете.
@ user1937198 И кстати, мое предложение использовать развернутый связанный список было всего лишь предложением по реализации. Предложенный выше FrozenMap соответствует моему определению «монотонных» распределений, как и неизменяемые и «замороженные» (я только что открыл для себя этот термин) структуры данных в целом. FrozenMap должен хорошо работать с алгоритмом hashbrown, и я уверен, что именно поэтому этот метод реализации был выбран вместо моего.
@user1937198 user1937198 Также я прошу прощения за злоупотребление термином «распределитель». Когда я говорю о разных распределителях, я говорю о разных шаблонах распределения (а не о разных методах распределения), что (я уверен) и имеется в виду под художественным термином Rust. Извините за мой запоздалый ответ, я сейчас смотрю президентские дебаты в США.
@user1937198 user1937198 «в системе типов ржавчины нет способа доказать, что два значения не равны». Да, я согласен, это, безусловно, самая сложная часть реализации монотонной хэш-карты (но не монотонного распределения в целом). Я не уверен, что это полностью соответствует духу Rust (не думаю, что это подойдет std), но это не обязательно должно применяться статически, может быть достаточно паники в режиме отладки. Кроме того, это просто проблема с хэш-картами, и она не отвечает на вопрос «Могу ли я доказать монотонность распределений» в целом.
@ user1937198 На самом деле, после поиска оказывается, что std действительно может паниковать. Но такая хэш-карта не будет работать с no_panic.
@WilliamRyman Это не то, что вы можете легко сделать с помощью дженериков (механизм статической диспетчеризации, который вы предлагаете), потому что для того, чтобы то, что вы предлагаете, работало в Rust, требуется, чтобы мутирующие методы использовали общую ссылку (& вместо &mut), что и делает elsa::FrozenMap, например. Вы не можете параметризовать, является ли ссылка общей или эксклюзивной, в любом случае это не приведет к ужасному загрязнению API. (Могут быть какие-то трюки, которые вы можете проделать со связанными типами, но это определенно кажется чем-то достаточно нишевым, чтобы гарантировать собственный правильный тип.)
@WilliamRyman Другими словами, насколько я понимаю, невозможно, чтобы метод insert карты принимал &self или &mut self в зависимости от некоторого общего типа, если вы хотите сохранить синтаксис метода (map.insert(...)). Потенциально у вас может быть несколько блоков impl, один с версией &self и один с версией &mut self, но только если вы сможете убедить компилятор, что реализации не могут существовать одновременно, и доказать, что impl не пересекаются с компилятор не всегда прост.
@cdhowie Ах, это имеет смысл. Спасибо за ответ.
Шаг 1, чтобы задать вопрос по SO: предоставьте воспроизводимый пример, с которым люди смогут поиграть.
Ответы 1
Прежде всего, если вам нужна только компиляция кода, то вы действительно можете относительно легко добиться этого с помощью небольшого клонирования и собственных ключей: посмотрите игровую площадку.
Хотя это немного скучно, не так ли?
Итак, что нам нужно, чтобы иметь возможность перебирать и ссылаться на ключ и значения карты при ее изменении?
Слейте, слейте, слейте!
(Не путайте с «лизать, лизать, лизать!», при этом ответе ни один геолог не пострадал)
В Rust утечка информации безопасна. На самом деле, для этого существует явная функция. Итак, мы собираемся слить все:
- Ключи будут
&'static str. - Команды будут
&'static [Command].
Утечку String можно добиться, выполнив следующие действия:
let filename: Box<str> = _string_;
let filename = Box::leak(filename);
И утечки среза можно добиться, выполнив:
let commands: Box<[Command]> = _vec_;
let commands = Box::leak(commands);
Вот и все. Теперь у нас есть HashMap<&'static str, &'static [Command]> где filepath: &'static str в Command::Subfile, и все готово.
Настройте это.
Утечка безопасна, так что это круто, но... повторению она не особо поддается. Поэтому нам нужен другой вариант.
Другим вариантом было бы, чтобы карта гарантировала, что вставленные ключи и значения не будут (1) перемещены и (2) не будут изменены (при совместном использовании).
Что очень круто в Rust, так это то, что вы можете выражать такие инварианты (разделяемые и неразделяемые) на уровне типа, поэтому мы получаем:
impl<K, V> PushMap<K, V> {
// Only reads & `insert_if_new` are possible for the duration of the borrow.
fn get(&self, key: &K) -> Option<&V>;
// Returns `value` if the key is already present in the map.
//
// This is unlike `insert` (which returns the previous value), hence the
// the different name.
fn insert_if_new(&self, key: K, value: V) -> Option<(K, V)>;
// Mirror API of standard HashMap.
fn get_mut(&mut self, key: &K) -> Option<&mut V>;
fn insert(&mut self, key: K, value: V) -> Option<V>;
fn remove(&mut self, key: &K) -> Option<V>;
}
Использование insert_new требует внутренней изменчивости. Внизу это означает UnsafeCell, а обертки Cell и RefCell здесь не подойдут, поэтому нам нужно будет создать свою собственную.
Это также означает, что НЕ будет возможно совместно использовать &PushMap в нескольких потоках (хотя это возможно с &HashMap), если мы также не сделаем это одновременной картой. Это компромисс.
Точная реализация оставлена читателю в качестве упражнения. Судя по литературе, типичная реализация хеш-таблицы со связанными списками в качестве сегментов отвечает всем требованиям, хотя использование связанных списков сопряжено с накладными расходами. В противном случае также возможна реализация на основе концепции Jagged Array, см. пример jagged репозиторий.
Отсутствие типов затрудняет проверку, но
&'a mut T<'a>почти всегда неверно. Вашvisited_file_cacheвыглядит вот так, поэтому вы можете столкнуться с Почему этот изменяемый заимствование выходит за рамки его возможностей? Попробуйте использовать разные времена жизни для ключей и внешней ссылки (или в этом случае вы, вероятно, можете просто опустить'aвообще, и компилятор будет определять разные времена жизни, если с'aбольше ничего не связано).