rust-embedded / rust-embedded/heapless

Bug: IndexMap fails to insert more than u16::MAX keys.

Open
#579 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
2k
Forks
253
Avg merge
1d 2h
Merged PRs (30d)
1

Description

I ran into this bug when inserting a lot of keys in an IndexMap, and it turns out that when my keys are bigger than an u16 they are not inserted properly. Here is a minimal reproducible code.

use heapless::FnvIndexMap;

fn main() {
    const N: usize = 1 << 17;
    let mut map = FnvIndexMap::<u32, usize, N>::new();
    for i in 1..(0xffff + 3) {
        let block = i;
        let idx = i as usize - 1;
        map.insert(block, idx).unwrap();
        assert!(map.contains_key(&block), "{}", i);
    }
}

I have no idea on why this happens. Does anyone have an idea ?
EDIT: the issue is not the values but the number of keys to insert shifting the start and end of the loop leads to the same bug
EDIT 2: the bug is present in the 0.8.0 version but fixed in 0.9.0 and on the latest commit on master.
EDIT 3: the bug is not fixed in any versions

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the minimal reproducer using FnvIndexMap::insert and contains_key, then trace the IndexMap implementation around insertion and lookup for capacities above u16::MAX. Done means the reproducer can insert and find all keys beyond that boundary without failure.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.