Doc request: what modification is allowed to RawTable while holding RawIter

[CAD97]

More context on urlo and my questionable code.

What operations are allowed on RawTable while holding a RawIter?

Per my reading, the implementation currently suggests:

• Required(?) for exposed behavior:
  • non-mutating inspection of the RawTable
  • eraseing the most recently yielded Bucket
• Definitely not allowed (UB):
  • anything that causes a reallocation
  • erasing a bucket "ahead" of the iterator that has yet to be yielded
• Potentially allowed:
  • erasing a bucket "behind" the iterator head that has previously been yielded but is not the most recently yielded bucket

I would benefit from the above "delayed erasing" being guaranteed sound (for the use case linked above).

Side note: it would be useful to make RawIter's debug_assert that it iterated all the expected items say what went wrong. Something simple like "exhausted iterator before expected; this likely indicates modification of a hash table while iterating it, which is UB" would definitely make hitting that assertion more obvious than the default message of "200 != 0" from inside of hashbrown's internals.

[Amanieu]

This feels like something extremely fragile to rely on since we could, for example, in the future decide to iterate backwards because we've changed our internal representation.

Looking at your code, is it really necessary to process the to_drop list while iterating? Can't you just process that list after the initial iteration to find dead "roots" has finished?

[CAD97]

Yeah, after sleeping on it, I realize that doing that would work, and do so without any impact on asymptotic complexity or space usage, and negligible impact on actual space usage.

It'd still probably be nice to say what's guaranteed to work: at the least, erasing the bucket most recently yielded by the iterator needs to be allowed for retain to work IIUC.

[jonhoo]

@CAD97 I'm not sure if it's relevant to your use-case, but #167 may be of interest to you.