slotmap VS miri

It looks like .get_disjoint_mut() from slotmap failed under stacked borrows, but seems to pass under tree borrows

I think slotmap is meant to solve this exact issue. Basically when you insert into a collection you get an Id:Version tuple as key. When you reuse a slot, next time the key will be Id:Version+1 and when you try to access the removed value by using Id:Version, it will return None. You can think about it as delayed invalidation.

Dunno about existing implementations, but it looks like it's a feature they'd accept: https://github.com/orlp/slotmap/issues/73

It's actually quite easy.

You can use either slot map or slab to side step rust borrow checker. Example https://github.com/orlp/slotmap/blob/master/examples/rand_meld_heap.rs

I don't know, only have some theories.

1. The name isn't particularly catchy or descriptive. It is the correct name for the data structure, but not too many people know the data structure.

2. People don't even know what they're missing. It's not a very Google-able problem to begin with. Slotmap provides an interesting solution to (circular) ownership and safe allocator / weak pointer design problems, but people don't recognize that they're having them or that slotmap could help.

As an example of this, the doubly linked list example (https://github.com/orlp/slotmap/blob/master/examples/doubly_...) can safely remove nodes from the linked list given their handle, in O(1), even from the middle, completely safely and correctly, even in the presence of double deletions or ABA memory re-use. You can't replicate this with just pointers, without introducing heavy refcounting solutions.

Nope, it's perfectly safe: https://github.com/orlp/slotmap/blob/master/examples/doubly_linked_list.rs.

I think keeping the relationship between child and parent elements in the node graph might be better accommodating better via a psuedo-ECS system, see https://www.reddit.com/r/rust/comments/cnjhup/idiomatic_way_to_reference_parent_struct/. The https://github.com/orlp/slotmap crate looks promising. I think I'm just going to ditch the global shared HashMap in favor of something that can better accommodate child/parent relations.

I think the slotmap crate is similar to what you're trying to write: https://github.com/orlp/slotmap

>While we are many missing language features away from this being the case, the noalias case is also magic descended upon box itself, with no user code ever having access to it.

I'm not sure why the author thinks there's magic behind Box. Box is not a special case of `noalias`. Run this snippet with miri and you'll see the same issue: https://play.rust-lang.org/?version=stable&mode=debug&editio...

`Box` _does_ have an expectation that its inner pointer is not aliased to another Box (even if used for readonly operations). See: https://github.com/rust-lang/miri/issues/1800#issuecomment-8...)

Miri [0] is an interpreter for the mid-level intermediate representation (MIR) generated by the Rust compiler. MIR is input for more processing steps of the compiler. However miri also runs MIR directly. This means miri is a VM. Of course it's not a bytecode VM, because MIR is not a bytecode AFAIK. I still think that miri is a interesting example.

And why does miri exist?

It is a lot slower. However it can check for some undefined behavior.

[0]: https://github.com/rust-lang/miri

Provenance is a dynamic property of pointer values. The actual underlying rules that a program must follow, even when using raw pointers and `unsafe`, are written in terms of provenance. Miri (https://github.com/rust-lang/miri) represents provenance as an actual value stored alongside each pointer's address, so it can check for violations of these rules.

Lifetimes are a static approximation of provenance. They are erased after being validated by the borrow checker, and do not exist in Miri or have any impact on what transformations the optimizer may perform. In other words, the provenance rules allow a superset of what the borrow checker allows.

There has been discussion of doing this with MIRI, which would be easier than all of rustc.

This issue has been fixed: https://github.com/rust-lang/miri/issues/2964

Actually, I've done more advanced tests with MIRI (see https://github.com/rust-lang/miri/issues/2920 for example) which allowed me to fix some issues. I've also made the code compatible with loom, but I didn't found the time yet to write and execute loom tests. That's on the TODO-list, and I need to track it with an issue too.

He is one of the big brains behind Miri, which is a interpreter that runs on the MIR (compiler representation between human code and asm/machine code) and detects undefined behavior. Super useful tool for language safety, pretty interesting on its own.

I would also run your tests in Miri (https://github.com/rust-lang/miri) to try to cover more bases.