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

[Meinersbur]

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.

[Meinersbur]

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.

[klausler]

In D88793#2310581, @Meinersbur wrote:

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.

[Meinersbur]

In D88793#2312313, @klausler wrote:

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.

[klausler]

In D88793#2380571, @Meinersbur wrote:

In D88793#2312313, @klausler wrote:

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.

[klausler]

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

[klausler]

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

[Meinersbur]

Obsoleted by D91210

flang/include/flang/Parser/message.h

private:
   bool attachmentIsContext_{false};
   Reference attachment_;
 };
 
 class Messages {
 public:
   Messages() {}
   Messages(Messages &&that) : messages_{std::move(that.messages_)} {
-    if (!messages_.empty()) {
-      last_ = that.last_;
-      that.ResetLastPointer();
-    }
+    RestoreLast();
+    that.RestoreLast();
   }
   Messages &operator=(Messages &&that) {
     messages_ = std::move(that.messages_);
-    if (messages_.empty()) {
-      ResetLastPointer();
-    } else {
-      last_ = that.last_;
-      that.ResetLastPointer();
-    }
+    RestoreLast();
+    that.RestoreLast();
     return *this;
   }
 
   std::forward_list<Message> &messages() { return messages_; }
   bool empty() const { return messages_.empty(); }
   void clear();
 
   template <typename... A> Message &Say(A &&...args) {
     last_ = messages_.emplace_after(last_, std::forward<A>(args)...);
     return *last_;
   }
 
   void Annex(Messages &&that) {
-    if (!that.messages_.empty()) {
-      messages_.splice_after(last_, that.messages_);
-      last_ = that.last_;
-      that.ResetLastPointer();
-    }
+    RestoreLast();
+    that.RestoreLast();
   }
 
   void Restore(Messages &&that) {
     that.Annex(std::move(*this));
     *this = std::move(that);
   }
 
   bool Merge(const Message &);
   void Merge(Messages &&);
   void Copy(const Messages &);
   void ResolveProvenances(const AllCookedSources &);
   void Emit(llvm::raw_ostream &, const AllCookedSources &,
       bool echoSourceLines = true) const;
   void AttachTo(Message &);
   bool AnyFatalError() const;
 
 private:
-  void ResetLastPointer() { last_ = messages_.before_begin(); }
+  void RestoreLast() {
+    last_ = messages_.before_begin();
+    auto next{messages_.begin()};
+    auto end{messages_.end()};
+    while (next != end) {
+      last_ = next;
+      ++next;
+    }
+  }
 
   std::forward_list<Message> messages_;
   std::forward_list<Message>::iterator last_{messages_.before_begin()};
 };
 
 class ContextualMessages {
 public:
   ContextualMessages() = default;

flang/lib/Parser/message.cpp

return std::visit(
           },
           [](const auto &, const auto &) { return false; },
       },
       location_, that.location_);
 }
 
 void Messages::clear() {
   messages_.clear();
-  ResetLastPointer();
+  RestoreLast();
 }
 
 bool Messages::Merge(const Message &msg) {
   if (msg.IsMergeable()) {
     for (auto &m : messages_) {
       if (m.Merge(msg)) {
         return true;
       }
while (!that.messages_.empty()) {
       if (Merge(that.messages_.front())) {
         that.messages_.pop_front();
       } else {
         messages_.splice_after(
             last_, that.messages_, that.messages_.before_begin());
         ++last_;
       }
     }
-    that.ResetLastPointer();
+    that.RestoreLast();
   }
 }
 
 void Messages::Copy(const Messages &that) {
   for (const Message &m : that.messages_) {
     Message copy{m};
     Say(std::move(copy));
   }