Non-panicking alternative to Index trait? / .get()

Hello,

Every few years, the discussion about an abstracted trait over container types emerges. For example here: No common trait for Map types?

These usually hit the rocks on some of the finer points such as iteration behavior. But just about all containers have a .get() method.

Is there a trait that provides an abstracted .get? Ideally in std, or in a crate with "most favored nation status" i.e. crate that has so much adoption that everybody uses that crate instead of rolling their own. For example, serde.

The Index trait would be ideal except for the fact that it panics internally and I can't figure out a corresponding way to check if an index is valid without risking a panic.

Thank you.

1 Like

To start with the obvious, this is not possible in the general case. E.g., where the Key type is a superset of the collection's key set. For instance, if Key is a usize, then on 64-bit platforms there are 264 possible keys to index the collection. Most collections (sans ZSTs) are not going to have capacity available to ensure that indexing with usize::MAX does not panic.

There are cases where the Key type is guaranteed to be an equivalent set (or even a subset) of the collection's keys (perfect hash, u8 keys for collections with 256 values, etc). And I suspect this is what you are getting at. Then the question becomes "how do you guarantee that an Index impl does not panic?"

To generalize further, we would need to know how any function can be guaranteed non-panicking. While the language doesn't support a notion of "guaranteed infallibility", there are some tricks that can be used to achieve the desired result. For instance, the no-panic crate provides an attribute macro that forces the compiler to prove an annotated function does not panic. It isn't perfect (see the caveats listed in docs) but it's what is currently available.

Knowing this, let's write a test!

use no_panic::no_panic;
use std::ops::Index;

struct MyStruct {
    data: [u32; 256],
}

impl Default for MyStruct {
    fn default() -> Self {
        Self { data: [0; 256] }
    }
}

impl Index<u8> for MyStruct {
    type Output = u32;

    #[no_panic]
    fn index(&self, idx: u8) -> &Self::Output {
        &self.data[idx as usize]
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::hint::black_box;

    #[test]
    fn test_index() {
        let mine = MyStruct::default();

        for i in 0_u8..=255 {
            println!("Index {i} = {}", mine[i]);

            assert_eq!(black_box(mine[i]), black_box(0));
        }
    }
}

When I run this with cargo test, I get a compile error due to the panicking path in the debug build (see aforementioned caveats). On the other hand, cargo run --release -- --nocapture prints all 256 lines and the test passes.

I suppose one may conclude that the Index trait is actually what you want, iff you can do something like this example and ensure that the impl does not panic. Unfortunately, there doesn't seem to be a way to do that without hacks like this #[no_panic] annotation. (Although it allows any function to be annotated, including the top-most functions in your application...)


Edit: there is also the TryFrom trait, which can do something similar but provides Result instead of guaranteeing infallible indexing. It is unusual to use it this way, though.

#[derive(Copy, Clone)]
struct WrappedU32<'a>(&'a u32);

impl<'a> TryFrom<(&'a MyStruct, usize)> for WrappedU32<'a> {
    type Error = ();

    #[no_panic] // Annotated to prove it doesn't panic
    fn try_from(value: (&'a MyStruct, usize)) -> Result<Self, Self::Error> {
        match value.1 {
            0..=255 => Ok(WrappedU32(&value.0.data[value.1])),
            _ => Err(()),
        }
    }
}

impl WrappedU32<'_> {
    pub fn to_u32(self) -> u32 {
        *self.0
    }
}
    #[test]
    fn test_try_from() {
        let mine = MyStruct::default();

        // Iterate more than 256 indices to check fallibility
        for i in 0_usize..=512 {
            match WrappedU32::try_from((&mine, i)) {
                Ok(value) => {
                    let value = value.to_u32();
                    println!("Index {i} = {value}");

                    assert_eq!(black_box(value), black_box(0));
                }
                _ => println!("Index {i} = ERROR"),
            }
        }
    }

I suspect you're over-indexing on "non-panicking."

OP, did you by any chance want an index-like trait where operations return an Option or a Result, instead of panicking, or did you really mean an irrefutable mapping from Key to Value as @parasyte is assuming here?

1 Like

Only slightly, which is why I added the TryFrom addendum. I understand that a generic fallible index trait would be useful, and I have wondered myself why one doesn't exist in the standard library.

A crate like array-ops does provide such a trait with a fn get(&self, index: usize) -> Option<&Self::Output> method, as long as your type has the required trait bounds. There are other crates that have similar offerings like collectivity. But as far as the standard library goes, I think Index and TryFrom are the only options?

My experience is that traits are only provided where necessary (this may have some advantages but also disadvantages, but it's what I witness often in Rust). My question is: For which scenario is the abstraction needed? What kind of generic function, method, or data type shall be created with it?

There are also other inherent methods in std where I sometimes feel like a trait would be nicer. But I believe that's because using trait methods generally becomes a bit unhandy due to scoping rules (trait must be in scope to use its methods).

3 Likes

Good point. That always slows me down with the io / stream stuff that's implemented as traits. I have to think for a minute about what to include.

I want to create an interface that abstracts the data source away, and lets the caller use whatever. Array, Vec, HashMap, some user implemented type. crates.io has a half dozen things that would fit the bill, and almost all of them have near-zero usage.

The community needs a canonical "quasi-official" crate (or set of crates) that overlays some of the std functionality thats common across objects.

I think a huge part of the stumbling block here is often that it's hard to find a useful middle ground between "I need exactly this type because I care about its properties" and the existing "I don't really care I just need a stream of stuff" traits like Iterator and Read.

Or, of course, the all-purpose source: FnMut.

3 Likes

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.