search

orlp / slotmap

Slotmap data structure for Rust
zlib License
1.13k stars 70 forks source link

Could you expand on why slottable values must be `Copy`? #27

Closed peterjoel closed 5 years ago

peterjoel commented 5 years ago

The docs mention that a type must implement Copy due to "current stable Rust restrictions". Could you expand on that?

orlp commented 5 years ago

Sorry for the slow reply, I'm very busy at the moment. I'll have more time soon to work on my own projects.

The short answer used to be that unions require their members to be Copy in stable Rust. Whether this restriction is still necessary today with Rust updates and the introduction of MaybeUninit I have not researched.

I could have implemented slotmap in 100% safe code without unions, but this would've lead to some pretty large memory overhead. There used to be a slot map variant without this restriction (the BlockSlotMap) that I unfortunately removed in my excitement of developing the HopSlotMap, without considering this issue.

Since then I've come to regret removing this variant as it has legitimate uses (and avoids this restriction). I will bring it back once I continue work on slotmap.

peterjoel commented 5 years ago

Thanks for responding! That makes sense.

Judging by the fact that I still get an error for non-Copy union members in the current Rust beta, I would NOT expect this to be fixed in 1.36 along with stabilisation of MaybeUninit.

olson-sean-k commented 5 years ago

It would be great if BlockSlotMap could be re-introduced. I have some code where I can accept the memory overhead if it means I can use non-Copy types.

(Sorry for going off topic, but thanks for all the work you've put into this crate! It's great to have a good slot map implementation in Rust.)

AndreaCatania commented 5 years ago

This get closed, but without a final explanation. If you found a workaround to store a non copy object, can you please write it here? Otherwise can you please reopen this?

orlp commented 5 years ago

@AndreaCatania The workarounds are mentioned in the docs (although I do notice a typo just now, "Copy data" should be "non-Copy data"):

https://docs.rs/slotmap/0.3.0/slotmap/trait.Slottable.html

The workarounds are:

  1. Use nightly Rust and enable the unstable feature on slotmap.
  2. Store the non-Copy data in a SecondaryMap.
AndreaCatania commented 5 years ago

Thanks for the reply! My question was most to understand if finally was possible to store the non copy data directly inside the primary map. But seems not (yet?) doable.

I'll try to use the SecondaryMap then.

AndreaCatania commented 5 years ago

By the way, the reason why I've asked it is because use a secondary map is not easily doable in my case, and require to change a big part of the software.

orlp commented 5 years ago

Sorry, what you want is not available in stable Rust at the moment without introducing a lot of memory overhead in the internal implementation.

I will be reintroducing the BlockSlotMap Soon™ that can solve this as well.

Silhalnor commented 4 years ago

This page (and something on Pittsburgh) are the only Google results to "BlockSlotMap". Is it safe to assume this has not been reintroduced yet?

Or maybe it could be merged with SlotMap? (Or HopSlotMap?) Or would that be a bad idea? Just seems a little inelegant to have three variants of the same library.

cyphar commented 4 years ago

The "no-Copy" feature of BlockSlotMap exists in DenseSlotMap in version 0.4.0. For those who are wondering precisely what unstable features are missing, it's untagged_unions which is tracked here and boils down to "unions currently require T: Copy for all members because there is no !Drop trait which is what the real requirement should be" -- though there are other things stopping it from being stable.