Fix the README in instrusive_collections_examples

[ckaran]

This is related to #37.

I just realized that it is unsound to use Arc, Rc, or references within an intrusive collection as I described in the README. The issue is that I switched modes from nodes point to Things (which own nodes) to nodes point to other nodes. If you own the node, but it is a part of a Thing, then when the owning Thing is dropped, you now have dangling pointer. Rust's compilation rules would normally prevent this from being a problem, but because of the amount of unsafe code that I already have to use, it is easy to make a mistake and bypass the compiler checks. I'm going to work on fixing this once I get a little more done on the singly linked list.

[RustyYato]

Yep, I think I mentioned this in my previous review. You'll have to use raw pointers within the intrusive collections.

Note: you can now project through NonNull and Option which should make it easier to write these intrusive collections based on a small stripped down version of linked list that I wrote. I'll put that code up sometime this week if you want to see it.

[ckaran]

You did, but I didn't fully understand it until I started writing my own code. This is why I keep asking you to review everything, instead of my pushing even minor stuff to master; it's too easy to make a mistake.

I'd love to see what you write, it always makes things clearer for me. Thank you!

[RustyYato]

Ok, I'll document my new reviews as issues with a new review tag. That way we can track it and make sure these sorts of subtle issues get resolved.

[RustyYato]

@ckaran I pushed by experimentations to the branch linked-list-DO-NOT-MERGE in the temp folder. I won't be merging this in, as the name suggests, but feel free to take whatever you need from it. I'll keep this branch alive until your examples are complete. It looks like I started working on AVL trees, but I remember getting stuck here because I don't know how to implement AVL trees 😄, so there's a partial implementation of that there.

Some notes from this experiment:

• You need to avoid references as much as possible, this includes methods that take &self or &mut self. This caused me quite a few problems with MIRI.
• You can use NonNull<T> and Option<NonNull<T>> to encode "must be valid", or "must be valid or null". gfp-core will handle projections through both of these with the recently added UncheckedProjectTo and UncheckedInverseProjectTo. For Option<Field> it projects to an Option<Parent>, which is useful for "must be valid or null" because it handles the null checks automatically. (In fact, this is why I added Unchecked*ProjectTo)
• You need Cell/UnsafeCell/AtomicPtr somewhere down the line because you'll be storing Link/DoubleLink directly in some other type T. That other type needs to know that Link/DoubleLink could change even when you are holding a shared reference &T.
• Building on the last point, I don't think it's safe to ever get a mutable (exclusive) reference to T, Link, or DoubleLink. This would enforce that the reference has exclusive access to Link/DoubleLink, but these types are fundamentally shared. I don't know of a way to enforce this besides boxing the types and only handing out &T. There are some subtleties to explore here.