range end index 2 out of range for slice of length 1

[Niedzwiedzw]

panicked at /home/niedzwiedz/.cargo/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.4.0/src/map/core.rs:442:44: range end index 2 out of range for slice of length 1

this happens when using shift_insert

[cuviper]

Do you have a reproducer? Or can you at least get that with RUST_BACKTRACE=1?

[Niedzwiedzw]

sadly it's a wasm app and I don't have time to write a separate reproduction at the moment... but isn't this the problem?

    /// Remove an entry by shifting all entries that follow it
    ///
    /// The index should already be removed from `self.indices`.
    fn shift_remove_finish(&mut self, index: usize) -> (K, V) {
        // Correct indices that point to the entries that followed the removed entry.
        self.decrement_indices(index + 1, self.entries.len());

        // Use Vec::remove to actually remove the entry.
        let entry = self.entries.remove(index);
        (entry.key, entry.value)
    }

self.entries.len() should be self.entries.len() - 1 I think

EDIT: sorry I misread, ok I'll try to reproduce

[Niedzwiedzw]

use indexmap::IndexMap;

#[test]
fn test_indexmap() {
    let mut indexmap = IndexMap::<i32, ()>::new();
    indexmap.shift_insert(0, 0, ());
    indexmap.shift_insert(1, 0, ());
    indexmap.shift_remove(&0);
    println!("{indexmap:?}");
}

managed to reproduce

[Niedzwiedzw]

failures:

---- test_indexmap stdout ----
thread 'test_indexmap' panicked at /home/niedzwiedz/.cargo/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.4.0/src/map/core.rs:442:44:
range end index 2 out of range for slice of length 1
stack backtrace:
   0: rust_begin_unwind
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/std/src/panicking.rs:652:5
   1: core::panicking::panic_fmt
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/panicking.rs:72:14
   2: core::slice::index::slice_end_index_len_fail_rt
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/slice/index.rs:65:5
   3: core::slice::index::slice_end_index_len_fail
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/slice/index.rs:58:5
   4: <core::ops::range::Range<usize> as core::slice::index::SliceIndex<[T]>>::index
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/slice/index.rs:404:13
   5: core::slice::index::<impl core::ops::index::Index<I> for [T]>::index
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/slice/index.rs:17:9
   6: <alloc::vec::Vec<T,A> as core::ops::index::Index<I>>::index
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/alloc/src/vec/mod.rs:2905:9
   7: indexmap::map::core::IndexMapCore<K,V>::decrement_indices
             at /home/niedzwiedz/.cargo/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.4.0/src/map/core.rs:442:44
   8: indexmap::map::core::IndexMapCore<K,V>::move_index
             at /home/niedzwiedz/.cargo/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.4.0/src/map/core.rs:489:17
   9: indexmap::map::core::entry::OccupiedEntry<K,V>::move_index
             at /home/niedzwiedz/.cargo/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.4.0/src/map/core/entry.rs:259:9
  10: indexmap::map::IndexMap<K,V,S>::shift_insert
             at /home/niedzwiedz/.cargo/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.4.0/src/map.rs:467:17
  11: indexmap_shift_remove::test_indexmap
             at ./src/lib.rs:7:5
  12: indexmap_shift_remove::test_indexmap::{{closure}}
             at ./src/lib.rs:4:19
  13: core::ops::function::FnOnce::call_once
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/ops/function.rs:250:5
  14: core::ops::function::FnOnce::call_once
             at /rustc/3f5fd8dd41153bc5fdca9427e9e05be2c767ba23/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

[cuviper]

Weird, that passes for me, and on the playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=68145f844278a3b0fd1b9fcef815e882

[Niedzwiedzw]

❯ rustc --version
rustc 1.80.1 (3f5fd8dd4 2024-08-06)

❯ cargo tree
indexmap_shift_remove v0.1.0 (/tmp/indexmap_shift_remove)
└── indexmap v2.4.0
    ├── equivalent v1.0.1
    └── hashbrown v0.14.5

[Niedzwiedzw]

Weird, that passes for me, and on the playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=68145f844278a3b0fd1b9fcef815e882

that's not the same code I posted

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=68145f844278a3b0fd1b9fcef815e882

[cuviper]

Isn't it? I just tried copy/pasting again...

[Niedzwiedzw]

refresh the app, I have edited the comment in the meantime maybe it screwed something up :D

I'll post again just to be sure (also you have a playground link above)

[Niedzwiedzw]

use indexmap::IndexMap;

#[test]
fn test_indexmap() {
    let mut indexmap = IndexMap::<i32, ()>::new();
    indexmap.shift_insert(0, 0, ());
    indexmap.shift_insert(1, 0, ());
    indexmap.shift_remove(&0);
    println!("{indexmap:?}");
}

[cuviper]

OK, got it. The shift_remove doesn't matter since we don't get that far. The second shift_insert fails because the key already exists, but we can't possibly move it to a new index (== len()). I think that's probably a caveat that we really do have to fail on, but we could at least add a nicer assertion about it.

[cuviper]

(and yes, the edits weren't refreshing on my page)

[Niedzwiedzw]

so what should I check for in my code?

[Niedzwiedzw]

if key exists then max index must be indexmap.len()?

[cuviper]

New keys can insert at 0..=len() (inclusive), but updating existing keys can only move to 0..len() (exclusive). You can also use the entry API with vacant shift_insert or occupied move_index, which may make that difference clearer, and that's what the main shift_insert does itself.

I'll work on an assertion and a doc update about this.

[Niedzwiedzw]

maybe there could be a _checked() version which returns a result?

[cuviper]

Hmm, or try_, because I think checked methods usually return Option. Like so?

fn try_shift_insert(&mut self, index: usize, key: K, value: V) -> Result<Option<V>, (K, V)>

There's also the unstable HashMap::try_insert to think about, which errors on any existing keys. So if that stabilizes and we mirror our own IndexMap::try_insert, then we'd probably want try_shift_insert to act like that too.

So I don't know, maybe I've talked myself back to checked, which would only validate the index.

[cuviper]

(And later try_shift_insert_checked? :dizzy_face: At some point, we have to say "just use entry.")

[cuviper]

I implemented a different idea as insert_before in #340 -- maybe that is more useful for you? Please take a look and let me know what you think!

[cuviper]

I released insert_before in indexmap v2.5.0. If you want to pursue the _checked idea, please consider what I replied above and propose a specific function signature and its semantics. Otherwise, I think this problem is reasonably well solved.