Incorrect behavior of OrdMap::range() for certain inputs

[danielhenrymantilla]

Sometimes, when using the .range(prefix_key ..) pattern with an OrdMap, we don't get back the expected keys (sometimes less, sometimes more!).

• I've tried to reduce the failure case, unsuccessfully 😞, so here it comes: Gist

• By looking at the code, I suspect there is something wrong with the way Node::path_next() and friends work (sometimes a Vec::new() is returned when recursing, which leads to an empty path when it shouldn't). Sadly, I haven't been able to pin-point the exact error since I don't know well the way the Nodes logic works, and I don't have the time to dwelve into learning it 😅.

  • If you are seeing this, and do know what the exact logic behind the Nodes and the paths is, sprinkling a few comments here and there within those functions would already be quite helpful in order to debug the issue 🙂

  • Trick I have used to help me debug this

    my_dbg! macro that works in a generic context

    • requires +nightly or RUSTC_BOOTSTRAP=1 to work.

    // Add this to the `lib.rs` file, after the inner attrs
    #![feature(specialization)]
    trait MyDebug {
        fn to_debug_string (this: &'_ Self) -> String;
    }
    impl<T : ?Sized> MyDebug for T {
        default
        fn to_debug_string (_: &'_ Self) -> String
        {
            "<No debug impl>".into()
        }
    }
    impl<T : ?Sized + ::core::fmt::Debug> MyDebug for T {
        fn to_debug_string (this: &'_ Self) -> String
        {
            format!("{:?}", this)
        }
    }
    macro_rules! my_dbg {( $expr:expr $(,)? ) => (
        match $expr { expr => {
            eprintln!("[{}:{}:{}] {} = {:#?}",
                file!(),
                line!(),
                column!(),
                stringify!($expr),
                crate::MyDebug::to_debug_string(&expr),
            );
            expr
        }}
    )}

    ---