bug: NodeStamp does not work as expected when reusing nodes

[BugenZhao]

First of all, I'd like to express my appreciation for your excellent work!

However, I've found a bug that NodeStamp does not work as expected when reusing nodes.

Problems

indextree/src/id.rs

Lines 40 to 64 in 3eee154

	impl NodeStamp {
	pub fn is_removed(self) -> bool {
	self.0.is_negative()
	}
	pub fn as_removed(&mut self) {
	debug_assert!(!self.is_removed());
	self.0 = if self.0 < i16::MAX {
	-self.0 - 1
	} else {
	-self.0
	};
	}
	pub fn reuseable(self) -> bool {
	debug_assert!(self.is_removed());
	self.0 > i16::MIN
	}
	pub fn reuse(&mut self) -> Self {
	debug_assert!(self.reuseable());
	self.0 = -self.0;
	*self
	}
	}

New nodes are allocated with NodeStamp(0). When we decide to remove it, as_removed will be called so the stamp of the removed node will be turned to -1. Then if it's reused, the stamp will become 1. If we repeat this, the values of this stamp form a sequence of...

0, -1, 1, -2, 2, ..., 32766, -32767

Here comes the problem: -32767 is still considered reusable since it's greater than i16::MIN = -32768. So if we reuse it, then the stamp will become 32767. However, if we remove it again, we'll get a stamp of -32767 since self.0 < i16::MAX is now false, so we're actually reusing a stamp!

32766, -32767, 32767, -32767, 32767, -32767...

This breaks the assumption that we should use different stamps for different nodes, and the interfaces relying on this may behave incorrectly. For example...

use indextree::Arena;

fn main() {
    let mut tree: Arena<i32> = Arena::new();

    for i in 0usize.. {
        let id = tree.new_node(42);
        assert!(!id.is_removed(&tree));

        id.remove(&mut tree);
        assert!(id.is_removed(&tree));

        let new_id = tree.new_node(42);
        assert!(!new_id.is_removed(&tree));a
        assert!(id.is_removed(&tree), "i: {i}, id: {id:?}, new_id: {new_id:?}"); // <--

        new_id.remove(&mut tree);
    }
}

This code above panics during the 16385th loop.

thread 'main' panicked at 'i: 16384, id: NodeId { index1: 1, stamp: NodeStamp(32767) }, new_id: NodeId { index1: 1, stamp: NodeStamp(32767) }', src/bin/index_tree.rs:18:9

Possible Solutions

The root cause of this problem is that reusable always return true, which is not expected. So an intuitive solution could be correctly implementing this function.

  pub fn reuseable(self) -> bool {
      debug_assert!(self.is_removed());
-     self.0 > i16::MIN
+     self.0 > i16::MIN + 1
  }

However, I suppose it's worthwhile revisiting the meaning of stamp's existence. The ultimate purpose of reusing a node is to save memory, so using i16 seems not that convincing here. A node being unresuable means that we have to allocate a new node. For example, if we simply turn the stamp into an i64, we'll have much more chances to reuse a node. The cost of 6 extra bytes between i16 and i64 is much less than allocating a new node, not to mention the memory alignment that may erase the difference.

So I'm wondering whether it's acceptable to claim that indexing with or calling methods on a removed NodeId is always considered to be an undefined behavior, so that we can remove the stamp at all? This could make node reusing always available.