Expected Value, Found &str

I was building a B+Tree for a database project. I had a Value enum, either text or a child node, and I wanted one struct for both leaf and inner nodes.

Then I tried this:

bTree.insert("value");

Rust said no.

This post is the rabbit hole from that one line. The tree design is in Building a B+Tree in Rust: What I Got Wrong First.

The Error

error[E0308]: mismatched types
  --> src/b_plus_tree.rs:72:22
   |
72 |         bTree.insert("value");
   |               ------ ^^^^^^^ expected `Value`, found `&str`
   |               |
   |               arguments to this method are incorrect

it is because i was trying to pass &str into Value enum type okay so now this was a reminder about what i studied about enum in Rust from the docs at the start , consulted AI about the error and suggested this implementing this helper:

impl From<&str> for Value {
    fn from(s: &str) -> Self {
        Value::Text(s.to_string())
    }
}

// then doing this
bTree.insert(Value::from("value"));

or doing:

bTree.insert(Value::Text("value".to_string()));

That fixed it for now. But then I wanted to know what From actually does and why Rust cares.

From, Into, and TryFrom

From is a conversion trait telling rust how to convert a string into a value. we could also use #[derive] and rust compiler will write implementation for us.

documentation advise to implement From trait in every version after Rust 1.41, From conversion is not expected to fail , if we want a conversion that fail we can try TryFrom.

as i was trying to understand what does From do i found that there is another trait that does the opposite which is Into, when we implement from we get into for free.

it was not possible to implement From in 1.41 and earlier becase this was blocked by rust orphan rules.

What Are Orphan Rules?

what are orphan rules ?? => a part of Rust coherence system for any type that must be at most one impl Trait for Type in the whole program => stop us from impl a foreing Trait for a foregn Type both outside of the program => to do impl Trait For Type we must have one of these Type in the crate or Trait in the crate => insuring crates does not add incompatible impls for same trait and type.

So basically you can’t just impl any trait on any type from anywhere. One of them has to be yours.

orphan rules for generics are much more stricter. so i wanted to learn about this an example of generic types with a trait is:

impl<T> From<Wrapper<T>> for Vec<T> {
    fn from(w: Wrapper<T>) -> Self {
        w.0
    }
}

what we are saying here is that we build a Vector of type T from Wrapper of Type T and this T means that this trait work with any type.

Covered vs Uncovered Types

another thing i found out about is the Covered and Uncovered types.

uncovered:

T  // naked
From<T> // naked inside a trait

covered:

Vec<T>  , Wrapper<T>

it is something i do and use daily but i dont know the standard name of it in Rust , that is good.

i got here just because i wanted to be able to pass a node or string to be able to have the B+Tree Leaf and Inner Node as one struct which is in my mind will make implementation easy.

this is not allowed if T is naked:

impl<T> From<Wrapper<T>> for Vec<T> { }

T should not be naked otherwise it is going to be failure, if T is wrapped into some wrapper it is going to work.

All of this because i wanted bTree.insert("value") to compile.

Side Note: Why Not str?

While I was picking types for my tree keys I hit another thing, that i just went through in the last months while learning rust from documentation , received too much information and completely forgot about this.

str can not be declared as a type in a struct:

struct Page {
    key: str,
    // ...
}

why because the compiler does not know the size of this str it need to be something like this let a: str = 'wiw' with this the compiler knows the type.

So for now:

type Key = String;

now i wanted to give my keys the type of string but the other two databases implementation use a different im currently having my key as string in my mind a string can have all the type of indexes in databases , what is the index that can not fit into the key ???

Still don’t know the answer to that one.

What I Took Away

I learned what From does, that Into comes free with it, and what orphan rules are. Also covered vs uncovered types, which is a name for something I was already doing without knowing the name.

I eventually moved past the in-memory Value enum entirely. Nodes became disk pages with page_id instead of Box<Node>. That part is in the B+Tree post.

I’m glad bTree.insert("value") didn't compile. I know what orphan rules are now.

What’s Next

Next time I’m going back to the B+Tree. Simple insert and search. The Rust things is done for now.