Why is seemingly satisfied trait not satisfied?

help
1

Hey guys. I'm using the redb crate which has quite some confusing lifetimes which seem to be getting in the way of implementing generic traits. I've made some progress, however the following error has me confused. I'll try to include as much code as possible to demonstrate the error. I have this trait:

pub trait MyGet<'a, K, V>: Sized + redb::ReadableTable<K, V> + 'a
where
    for<'b> K: redb::Key<SelfType<'b> = K> + 'b,
    for<'b> V: redb::Value<SelfType<'b> = V> + 'b,
{
    fn my_get(&'a self, k: K) -> Result<Option<redb::AccessGuard<'_, V>>, redb::StorageError> {
        self.get(k)
    }
}

impl<'a, K, V> MyGet<'a, K, V> for redb::ReadOnlyTable<K, V>
where
    for<'b> K: redb::Key<SelfType<'b> = K> + 'b,
    for<'b> V: redb::Value<SelfType<'b> = V> + 'b,
{
}

The following test fails:

fn gets_table<K, V>() -> ReadOnlyTable<K, V>
where
    for<'b> K: redb::Key<SelfType<'b> = K> + 'b,
    for<'b> V: redb::Value<SelfType<'b> = V> + 'b,
{
    unimplemented!()
}

#[test]
fn test_my_get_with_borrow() {
    let table = gets_table::<&[u8; 16], &[u8; 16]>();
    table.my_get(&[0; 16]);
}

Output:

error[E0599]: the method `my_get` exists for struct `ReadOnlyTable<&[u8; 16], &[u8; 16]>`, but its trait bounds were not satisfied
   --> db/src/lib.rs:64:11
    |
64  |     table.my_get(&[0; 16]);
    |           ^^^^^^ method cannot be called on `ReadOnlyTable<&[u8; 16], &[u8; 16]>` due to unsatisfied trait bounds
    |
   ::: /home/u/.cargo/git/checkouts/redb-24e44532b0b35edd/a813740/src/table.rs:426:1
    |
426 | pub struct ReadOnlyTable<K: Key + 'static, V: Value + 'static> {
    | -------------------------------------------------------------- doesn't satisfy `_: MyGet<'_, &[u8; 16], &[u8; 16]>`
    |
note: trait bound `<&[u8; 16] as redb::Value>::SelfType<'b> = &[u8; 16]` was not satisfied
   --> db/src/lib.rs:42:26
    |
40  | impl<'a, K, V> MyGet<'a, K, V> for redb::ReadOnlyTable<K, V>
    |                ---------------     -------------------------
41  | where
42  |     for<'b> K: redb::Key<SelfType<'b> = K> + 'b,
    |                          ^^^^^^^^^^^^^^^^ unsatisfied trait bound introduced here
43  |     for<'b> V: redb::Value<SelfType<'b> = V> + 'b,
    |                            ^^^^^^^^^^^^^^^^ unsatisfied trait bound introduced here

For more information about this error, try `rustc --explain E0599`.
error: could not compile `db` (lib test) due to 2 previous errors

However within the redb crate, there are the following implementations:

pub trait Key: Value {
// ...
}

impl Value for &[u8] {
    type SelfType<'a> = &'a [u8]
    where
        Self: 'a;
// ...
}

impl<const N: usize> Value for &[u8; N] {
    type SelfType<'a> = &'a [u8; N]
    where
        Self: 'a;
// ...
}

I've tried my best to imitate the bounds of the crate but it is somewhat failing. I'm sure this is an issue of lifetimes, however the error message doesn't really communicate where exactly the error is. Could someone provide some guidance?

2 
    for<'b> K: redb::Key<SelfType<'b> = K> + 'b,

Just a random guess, what if you replace + 'b with + Captures<'b)> where Captures is this

trait Captures<'a> { }
impl<T: ?Sized> Captures<'a> for T { }
3

Thanks for the reply. I gave that a go. Adding that to the trait forced me to add 'static, and that didn't resolve the problem unfortuantly. The error message remains the same.

4

this bound is not satisfied.

in your test code, the type K is &'x [u8; 16] for some concrete lifetime 'x, but the bound said K must be unified with the associated SelfType<'b> for all lifetime 'b.

5

Database libraries usually write generic code with complex interactions on lifetimes and type parameters.
In that case, it's challenging for users to write correct code the compiler accepts...

For redb, there are at least two apparent 'static constraits on your used types:

pub trait ReadableTable<K: RedbKey + 'static, V: RedbValue + 'static>
pub struct ReadOnlyTable<'txn, K: RedbKey + 'static, V: RedbValue + 'static>

Thus

pub trait MyGet<'a, K, V>: Sized + redb::ReadableTable<K, V> + 'a
where
    for<'b> K: Key<SelfType<'b> = K> + 'static,
    for<'b> V: Value<SelfType<'b> = V> + 'static,

impl<'a, K, V> MyGet<'a, K, V> for ReadOnlyTable<'a, K, V>
where
    for<'b> K: Key<SelfType<'b> = K> + 'static,
    for<'b> V: Value<SelfType<'b> = V> + 'static,

fn gets_table<'a, K, V>(tx: &'a ReadTransaction) -> ReadOnlyTable<'a, K, V>
where
    K: for<'b> Key<SelfType<'b> = K> + 'static,
    V: for<'b> Value<SelfType<'b> = V> + 'static,

But with gets_table::<&[u8; 16], &[u8; 16]>, you'll see the same error as in OP.

Especially this hint:

note: trait bound `<&[u8; 16] as RedbValue>::SelfType<'b> = &[u8; 16]` was not satisfied

Due to K: 'static, &[u8; 16] should be &'static [u8; 16], so you should pass

fn test_my_get_with_borrow(tx: &ReadTransaction) {
    let table = gets_table::<&'static [u8; 16], &'static [u8; 16]>(tx);
    const A: &'static [u8; 16] = &[0; 16];
    table.my_get(A);
}

Well, same error! Why does <&[u8; 16] as RedbValue>::SelfType<'b> = &[u8; 16] break?

  • <&'static [u8; 16] as RedbValue>::SelfType<'b> = &[u8; 16] should be held,
  • but the other trait bound part for<'b> K: Key<SelfType<'b> = K> breaks the above constraint:
    • K = &'static [u8; 16], but SelfType<'b> is for any &'b [u8; 16]
    • &'b [u8; 16] is from an arbitrarily temporary variable in a function, it can never meet 'static !

I'd be surprised there is no [T; N]: RedbValue + RedbKey implemented in redb crate.
So you have to define a wrapper for [u8; 16]. This works.

2 Likes
6

Here's two alternative solutions.

Alternative 1

The get method you use need a Borrow bound with K::SelfType<'a> being bound. It means we can use the binding to know when the borrow happens (in an abstract way) !

//impl<'txn, K: RedbKey + 'static, V: RedbValue + 'static> ReadableTable<K, V> 
//for ReadOnlyTable<'txn, K, V> 
fn get<'a>(
    &self,
    key: impl Borrow<K::SelfType<'a>>
) -> Result<Option<AccessGuard<'_, V>>, StorageError>
where
    K: 'a,

With K and V being 'static as ReadableTable and ReadOnlyTable require, the lifetime parameter on MyGet<'a, ...> is moved to SelfType<'a> on K. This compiles:

pub trait MyGet<'a, K, V>: Sized + redb::ReadableTable<K, V>
where
    K: Key + Borrow<<K as redb::RedbValue>::SelfType<'a>> + 'static,
    V: Value + 'static,
{
    fn my_get(&self, k: K) -> Result<Option<redb::AccessGuard<'_, V>>, redb::StorageError> {
        self.get(k)
    }
}

impl<'a, K, V> MyGet<'a, K, V> for ReadOnlyTable<'_, K, V>
where
    K: Key + Borrow<<K as redb::RedbValue>::SelfType<'a>> + 'static,
    V: Value + 'static,

fn gets_table<'tx, 'a, K, V>(tx: &'tx ReadTransaction) -> ReadOnlyTable<'tx, K, V>
where
    K: Key + Borrow<<K as redb::RedbValue>::SelfType<'a>> + 'static,
    V: Value + 'static,

fn test_my_get_with_borrow_ok(tx: &ReadTransaction) { // compiles
    let table = gets_table::<&[u8; 16], &[u8; 16]>(tx);
    // i.e. let table = gets_table::<&'static [u8; 16], &'static [u8; 16]>(tx);
    table.my_get(&[0; 16]); // &[0; 16] is a static promotion, thus &'static [0; 16]
}

It also works for the wrapper type Array([0; 16]). But definitely not work for non-'static value!

fn test_my_get_with_borrow_actuall_not_ok(tx: &ReadTransaction) { // not compile
    let table = gets_table::<&[u8; 16], &[u8; 16]>(tx);
    //i.e. let table = gets_table::<&'static [u8; 16], &'static [u8; 16]>(tx);
    let arr_on_stack = [0; 16];
    table.my_get(&arr_on_stack); // error: `arr_on_stack` does not live long enough
}

Alternative 2

Since we have these bounds:

  • K: 'static, V: 'static (as ReadableTable and ReadOnlyTable require)
  • K: Borrow<K> (as defined in stdlib)
  • K: Borrow<<K as redb::RedbValue>::SelfType<'a>> for a given 'a (as ReadableTable::get require)

We must hold these (as alternative 1 does)

K: Key + Borrow<<K as redb::RedbValue>::SelfType<'a>> + 'static,
V: Value + 'static,

Once we specify K::SelfType<'a> to be K, 'a is meaningless in some way because we've forced the given 'a to be 'static. Then we can do this: it compiles

// no 'a or for<'b> anymore
pub trait MyGet<K, V>: Sized + redb::ReadableTable<K, V>
where
    K: Key<SelfType<'static> = K> + 'static,
    V: Value + 'static,

// As alternative 1 does, it works for 'static type (&'static [u8; 0] and Array),
// but definitely doesn't work for non-'static value!
1 Like
7

The above solves my problem for get, but unfortuantly for my specific circumstances, I need to compare a slice of keys with those of a range. Take for example the following where I have a range, and need to know if any key returned from the range, matches any element of the target slice, which we assume will be encountered in order (this next is sufficient for comparison):

    fn range_get(
        &'a self,
        min: K,
        max: K,
        targets: &mut [K],
    ) -> Result<impl Iterator<Item = (AccessGuard<'a, K>, AccessGuard<'a, V>)>> {
        let mut r = self.range(min..max)?;

        Ok(std::iter::from_fn(move || {
            while let Some(Ok(guard_tuple)) = r.next() {
                let k = guard_tuple.0.value();
                if targets.contains(&k) {
                    return Some(guard_tuple);
                }
            }
            None
        }))
    }

This will not compile since the keys returned by AccessGuard<'_ ,_>::value() are the type V::Selftype<'_> while target is K. To solve this problem, I attempted the prior for<'b> K: redb::Key<SelfType<'b> = K> + 'b, bound which we covered above. I also attempted various approaches using PartialEq, such as: for<'b> K::SelfType<'b>: PartialEq<K>, but that gives me lifetime errors everywhere:

error[E0505]: cannot move out of `guard_tuple` because it is borrowed
   --> db/src/domain/traits.rs:141:33
    |
137 |             while let (Some(Ok(guard_tuple)), Some(next_target)) = (r.next(), target) {
    |                                ----------- binding `guard_tuple` declared here
138 |                 let k = guard_tuple.0.value();
    |                         ------------- borrow of `guard_tuple.0` occurs here
...
141 |                     return Some(guard_tuple);
    |                                 ^^^^^^^^^^^ move out of `guard_tuple` occurs here
142 |                 }
143 |             }
    |             - borrow might be used here, when `k` is dropped and runs the destructor for type `<K as redb::Value>::SelfType<'_>`

Do you have any advice for the above issue?

8

This works.

For no matter what solution, K and V must be 'static as long as methods from ReadableTable is called.

pub trait MyGet<K, V>: Sized + redb::ReadableTable<K, V>
where
    K: for<'a> Key<SelfType<'a> = K> + PartialEq + 'static,
    V: Value + 'static,
{
    fn my_get(&self, k: K) -> Result<Option<redb::AccessGuard<'_, V>>, redb::StorageError> {
        self.get(k)
    }

    fn range_get<'s>(
        &'s self,
        min: K,
        max: K,
        targets: &mut [K],
    ) -> Result<impl Iterator<Item = (AccessGuard<'s, K>, AccessGuard<'s, V>)>> {
        let mut r = self.range(min..max)?;

        Ok(std::iter::from_fn(move || {
            while let Some(Ok(guard_tuple)) = r.next() {
                let k = guard_tuple.0.value();
                if targets.contains(&k) {
                    return Some(guard_tuple);
                }
            }
            None
        }))
    }
}
1 Like
9

Thank you for the help. It's a pity that the solution requires me to implement my own type but at least I can proceed.

10

FYI in the last link (where contents are updated in same link on rustexplorer)

  1. you can define a const array to have any length
#[derive(Debug, PartialEq)]
struct Array<const N: usize>([u8; N]);
  1. you can have V = &'static [u8; 16] work, but 'static can be inferred/elided.
gets_table::<Array<16>, &[u8; 16]>() // compiles
1 Like
11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.