I have a Trie and I'm building it up with a convenience &str function like so:
pub fn from_str_list(list: &[&str]) -> Trie<'t, char> {
let mut trie = Trie::default();
for word in list {
// I get mutable borrow starts in previous iteration of
// loop error
trie.insert_seq(&word.chars().collect::<Vec<_>>());
}
trie
}
is there any safe or unsafe way to do this?
Can you provide the exact error message (or better yet, a runnable example on the playground)? There's not really enough information here to figure out the issue.
You're creating trie on the stack, and then wanting to return it. You wouldn't even want to use unsafe code, because it would get dropped from the stack once the closure finished. If you want to pass-on trie, perhaps you can do something like this:
// get rid of Trie<'a, char> and replace with Trie<char> IF the only field in Trie that has lifetime 'a is the variable obtained from word.chars().collect::<Vec<_>>()
// I also add <'a> in (not actually needed as they are elided) to show that the lifetime of "whatever calls from_str_list" has a lifetime of a
pub fn from_str_list<'a>(list: &'a [&'a str], trie: &'a mut Trie<char>) {
for word in list {
// I get mutable borrow starts in previous iteration of
// loop error
trie.insert_seq(word.chars().collect::<Vec<_>>()); // remove reference
}
}
And then call it:
let mut trie = Trie::default();
from_str_list(&["value1", "value1"], &mut trie); // each have a lifetime of 'a
If you are truly insane (don't do this, lol):
pub fn from_str_list(list: &[&str]) -> Trie<'t, char> {
let mut trie = Trie::default();
for word in list {
// I get mutable borrow starts in previous iteration of
// loop error
// does insert_seq need &T or T for the vector input? Not enough info to correctly set this up
(&mut trie).insert_seq(&word.chars().collect::<Vec<_>>());
}
unsafe { std::mem::transmute(trie) }
}
Just to be clear the second one that @nologik showed is also UB.
You could even have the signature,
fn from_str_list(list: &[&str]) -> Trie<char>
If you don't have a lifetime parameter on Trie
Yea sorry about that, I expected you to read my mind! I'll try to get a working playground later today.
The problem is when trying to implement compression I added the Node.parent field which forced me to add all the lifetimes to &mut self's effectively "pinning" any mut borrow to the whole lifetime of the Trie.
relevant type signature
pub struct Trie<'t, T> {
pub(crate) children: Vec<Node<'t, T>>,
child_size: usize,
}
pub fn insert_seq(self: &'t mut Trie<'t, T>, vals: &[T])
fn insert_rest(vals: &[T], node: Option<&'t mut Node<'t, T>>, mut idx: usize)
fn push_return(&mut self, val: Node<'t, T>) -> Option<&mut Node<'t, T>>
pub(crate) struct Node<'a, T> {
pub(crate) val: T,
// this self reference is the problem
parent: Cell<Option<&'a Node<'a, T>>>,
children: Vec<Node<'a, T>>,
compress: Vec<T>,
child_size: usize,
terminal: bool,
}
// adds then returns the just added node
pub(crate) fn add_child(&'a mut self, n: Node<'a, T>) -> Option<&mut Node<'a, T>>
parent references are very hard to do in Rust, try and avoid them. They almost always lead to self-referential types, and those are very hard to work with.
I recommend using indexes into a Vec instead of references.
The problem with this (I realize I went to light on the example so it was not clear) the parent is the node that contains the current child not a node in the current vec.
I'm probably way off but just as a reference my attempt playground and before I tried to add parent ref github.
An ECS approach using indexes, as @alice suggests, is frequently the best way to address problems like these.
The thread topic asks "Is there any unsafe way around borrow checker?" The answer is that the unsafe keyword is the way around the borrow checker, but it cannot provide protection from the UB that ensues when LLVM mis-compiles your program because you violated the input constraints that LLVM imposes, which the borrow checker ensures.
The curse of a very-highly-optimizing compiler such as LLVM is that it can trash your program if you violate its input requirements – if not in the current compiler release, then likely in some future, improved release. Thus any code with UB is fragile at best, and completely untrustworthy in the long haul.
Yea my title is terrible I wasn't sure if changing it was frowned upon after getting answers. My original question wasn't what I actually needed. In the future should I edit the title?
That argument against unsafe is great I didn't know that about LLVM!
I'd leave the thread title, as this will happen to other users and they will find it better this way. I think this is an important part of learning rust / why rust makes these choices.
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.