[llvm-dev] ilist/iplist are broken (maybe I'll fix them?)

[Duncan P. N. Exon Smith via llvm-dev]

> On 2015-Oct-08, at 13:56, escha <escha at apple.com> wrote:
> 
> 
>> On Oct 8, 2015, at 11:00 AM, Justin Bogner via llvm-dev <llvm-dev at lists.llvm.org> wrote:
>> 
>> "Duncan P. N. Exon Smith" <dexonsmith at apple.com> writes:
>>> I don't feel totally comfortable just going ahead and fixing this
>>> without buy-in, since it'll touch some things.  Here's my basic plan:
>>> 
>>> - Fix `getNextNode()` and `getPrevNode()` by taking in the parent list
>>>   and checking against `end()` instead of checking for `nullptr`.
>>> - Change the lists to be normal circular linked lists (possibly I'll
>>>   stick an "is-sentinel" bit in the prev pointer in asserts builds so
>>>   we can have assertions instead of infinite loops).  I'll layer our
>>>   weird partial ownership semantics on top to keep this part NFC.
>>> - Re-layer the external state hooks so that they're on top of the
>>>   basic list instead of inside of it (so that someone in the future
>>>   can understand the code with far less studying).
>>> 
>>> Anyone want to back me on this before I dive in?  Even better, did I
>>> miss something fundamental?
>> 
>> +1
>> 
>> Other than having to update pretty well the entire code base, I don't
>> see any drawbacks to replacing ilist/iplist with something sane. The
>> current thing is complicated, tries to do too many things (and not many
>> of them well), and broken in several ways. In addition to the UB and
>> re-capitation you mention, I've also heard of issues using the reverse
>> iterators.
> 
> Specifically, I discovered (the hard and painful way) last night that if you reverse-iterator over a MachineBasicBlock, removing/moving instructions as you go — even pre-incrementing the iterator at the start of the loop isn’t enough to prevent the list from being corrupted in unexpected ways. A regular iterator, used backwards (-- instead of ++) works correctly, nothing else different.

This is because instead of ilist/iplist implementing a list-specific
reverse iterator, they use std::reverse_iterator, which is wholly
inappropriate for a list.  std::reverse_iterator is designed for
places where you can't increment past-the-begin.  Dereferencing works
like this:
--
T &operator*() const {
  return *std::prev(I);
}
--
and it holds a iterator to the "next" node from the one you expect it
to.  Basically, iteration works, but the iterator isn't valid when
you modify the list.

I can write a proper list reverse_iterator while I'm in there.