This is an archive of the discontinued LLVM Phabricator instance.

[flang] Fix assumptions on std::forward_list iterator implementation.
AbandonedPublic

Authored by Meinersbur on Oct 4 2020, 12:38 AM.

Details

Summary

The code in the messages class makes several assumptions how std::forward_list is implemented which are not guaranteed by the standard. It fails, e.g. with Microsoft's STL implementation.

  1. Use of container A's iterator for container B after a move or merge of elements of A into B. This is not allowed for any STL container.
  2. Use of B's before_begin sentinel iterator for A after B has been moved-assigned to A. Like the other iterators, the before_begin iterator is specific their container. MS STL's implementation is probably the only correct here since the before_begin iterator has no precondition an should still be valid after its content has been replaced by a move-assignment.

Remove dependence on implementation details by restoring the last_ from the container's own iterators.

Diff Detail

Event Timeline

Meinersbur created this revision.Oct 4 2020, 12:38 AM
Herald added a project: Restricted Project. · View Herald Transcript
Meinersbur requested review of this revision.Oct 4 2020, 12:38 AM

There seems to be no good reason for this strategy. Possible other implementations:

  1. Use of std::deque which all direct insertion at the end. It also does not require an heap allocation for every element inserted.
  2. Use of std::vector. When emitting diagnostics, all elements are copied to a std::vector anyway.
  3. Insertion and the beginning of std::forward_list. Again, the list is sorted anyway before messages are printed.

There seems to be no good reason for this strategy. Possible other implementations:

  1. Use of std::deque which all direct insertion at the end. It also does not require an heap allocation for every element inserted.
  2. Use of std::vector. When emitting diagnostics, all elements are copied to a std::vector anyway.
  3. Insertion and the beginning of std::forward_list. Again, the list is sorted anyway before messages are printed.

The point is to use std::forward_list::splice_after() for efficient combination of messages.

The point is to use std::forward_list::splice_after() for efficient combination of messages.

Unfortunately it also means that we have to search for the new last element since we cannot assume that iterators of the consumed list became iterators for the resulting list. This probably eats up any potations savings. There isn't a a guarantee that splice_after is O(1) anyway.

The point is to use std::forward_list::splice_after() for efficient combination of messages.

Unfortunately it also means that we have to search for the new last element since we cannot assume that iterators of the consumed list became iterators for the resulting list. This probably eats up any potations savings. There isn't a a guarantee that splice_after is O(1) anyway.

I'll replace the forward_list with a custom container, then.

Please see D91210 for a replacement implementation in terms of std::list<>.

Is this particular concern now resolved by the change to std::list<>?

Meinersbur abandoned this revision.Dec 10 2020, 8:36 AM

Obsoleted by D91210