Support miri

[CryZe]

The crate does not seem to work well with miri at the moment for multiple reasons. One reason is that the crate uses the x86 / C implementations over the fallback implementation, which miri doesn't support. But even when cfg'ing out those implementations via cfg(miri), the fallback implementation uses a lot of bit math on pointers, which miri also doesn't like.

[BurntSushi]

I don't have any experience with miri, so I'm not really sure what to do with this bug report. As it is, it isn't actionable, as I don't know what outcome you're hoping for here in terms of this crate in particular. It sounds like this is a bug for miri, not memchr.

[CryZe]

Yeah, as cargo miri test is still fairly new, it is expected that it isn't able to handle all rust code just yet. Especially with the heavy focus on const evaluation in miri, a lot of other things are currently entirely forbidden, such as the bit math on the pointers in memchr. So yes, this is likely a bug in miri I would assume. I'll open an issue there and see what the plans are for pointer math outside of const eval. Depending on their stance on whether they want to allow this at all, I was hoping you may be willing to accept a PR with some #[cfg(miri)] that would solve the problem in a miri compatible way. Another alternative would be for me to rip out the memchr dependency when targeting miri, but if memchr became miri compatible, it would help miri adoption across the ecosystem.

[BurntSushi]

I was hoping you may be willing to accept a PR with some #[cfg(miri)] that would solve the problem in a miri compatible way

I figured as much, but I don't know if I would be or not, because I don't know what it would entail and what the consequences would be. Some brief thoughts:

• Writing a naive implementation of all the functions in this crate is very simple. Likely a single line for most. Indeed, it looks like they already exist. I assume those implementations would work fine with miri.
• What are the consequences of having completely different code running under miri than would run otherwise?
• How does miri deal with raw pointer heavy code in std and other libraries?

[abonander]

What are the consequences of having completely different code running under miri than would run otherwise?

The idea isn't necessarily to test memchr in Miri, it's to test user code. As long as memchr remains correct I don't see a problem with it using different code. Fuzz testing can (at least somewhat) cover the gaps.

[abonander]

Also looks like Miri just got fixed to support bit math on pointers: rust-lang/rust#63839

[BurntSushi]

If there's a simple patch that someone wants to submit that would improve quality of life for miri users, then I think I'd be happy to accept it.

[ldesgoui]

Hello, I got memchr to run on MIRI by adding more cfg directives.
I could PR it as is (minimal changes) but I really feel like this deserves using cfg_if.

pub fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> {
    cfg_if::cfg_if! {
        if #[cfg(miri)] {
            let imp = naive::memchr;
        } else if #[cfg(all(target_arch = "x86_64", memchr_runtime_simd))] {
            let imp = x86::memchr;
        } else if #[cfg(memchr_libc)] {
            let imp = c::memchr;
        } else {
            let imp = fallback::memchr;
        }
    };

    ...
}

vs

pub fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> {
    #[cfg(miri)]
    #[inline(always)]
    fn imp(n1: u8, haystack: &[u8]) -> Option<usize> {
        naive::memchr(n1, haystack)
    }

    #[cfg(all(not(miri), target_arch = "x86_64", memchr_runtime_simd))]
    #[inline(always)]
    fn imp(n1: u8, haystack: &[u8]) -> Option<usize> {
        x86::memchr(n1, haystack)
    }

    #[cfg(all(
        not(miri),
        not(target_arch = "x86_64"),
        not(memchr_runtime_simd),
        memchr_libc,
    ))]
    #[inline(always)]
    fn imp(n1: u8, haystack: &[u8]) -> Option<usize> {
        c::memchr(n1, haystack)
    }

    #[cfg(all(
        not(miri),
        not(memchr_libc),
        not(target_arch = "x86_64"),
        not(memchr_runtime_simd),
    ))]
    #[inline(always)]
    fn imp(n1: u8, haystack: &[u8]) -> Option<usize> {
        fallback::memchr(n1, haystack)
    }

    ...
}

What would be your preference, @BurntSushi?
Thank you.

[BurntSushi]

@ldesgoui Thanks! I think submitting a PR as is would be great. I'd really like to try to avoid additional dependencies. (memchr once used cfg_if, but I ripped it out. To make the cfgs easier to reason about, the build script does a bit of the heavy lifting.)

[ldesgoui]

Sounds good to me, coming right up!

[BurntSushi]

@ldesgoui Yeah, that diff looks fine to me. It doesn't really make the current situation much worse.