[flang][MSVC] Use list<Message> rather than forward_list<> in Messages

[klausler]

Summary

The implementation of Messages with forward_list<> makes some
nonstandard assumptions about the validity of iterators that don't
hold up with MSVC's implementation. Use list<> instead. The
measured performance is comparable.

This change obviated a distinction between two member functions
of Messages, and the uses of one have been replaced with calls
to the other.

Similar usage in CharBuffer was also replaced for consistency.

[tskeith]

flang/include/flang/Parser/message.h

23

Is this needed?

[klausler]

flang/include/flang/Parser/message.h

23

No, it's left over from a performance measurement experiment; will remove.

[klausler]

Remove needless <deque>

[Meinersbur]

LGTM

flang/include/flang/Parser/char-buffer.h

 //===-- include/flang/Parser/char-buffer.h ----------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef FORTRAN_PARSER_CHAR_BUFFER_H_
 #define FORTRAN_PARSER_CHAR_BUFFER_H_
 
 // Defines a simple expandable buffer suitable for efficiently accumulating
 // a stream of bytes.
 
 #include <cstddef>
-#include <forward_list>
+#include <list>
 #include <string>
 #include <utility>
 #include <vector>
 
 namespace Fortran::parser {
 
 class CharBuffer {
 public:
   CharBuffer() {}
   CharBuffer(CharBuffer &&that)
-      : blocks_(std::move(that.blocks_)), last_{that.last_},
-        bytes_{that.bytes_}, lastBlockEmpty_{that.lastBlockEmpty_} {
+      : blocks_(std::move(that.blocks_)), bytes_{that.bytes_},
+        lastBlockEmpty_{that.lastBlockEmpty_} {
     that.clear();
   }
   CharBuffer &operator=(CharBuffer &&that) {
     blocks_ = std::move(that.blocks_);
-    last_ = that.last_;
     bytes_ = that.bytes_;
     lastBlockEmpty_ = that.lastBlockEmpty_;
     that.clear();
     return *this;
   }
 
   bool empty() const { return bytes_ == 0; }
   std::size_t bytes() const { return bytes_; }
 
   void clear() {
     blocks_.clear();
-    last_ = blocks_.end();
     bytes_ = 0;
     lastBlockEmpty_ = false;
   }
 
   char *FreeSpace(std::size_t &);
   void Claim(std::size_t);
 
   // The return value is the byte offset of the new data,
   // i.e. the value of size() before the call.
   std::size_t Put(const char *data, std::size_t n);
   std::size_t Put(const std::string &);
   std::size_t Put(char x) { return Put(&x, 1); }
 
   std::string Marshal() const;
 
 private:
   struct Block {
     static constexpr std::size_t capacity{1 << 20};
     char data[capacity];
   };
 
   int LastBlockOffset() const { return bytes_ % Block::capacity; }
-  std::forward_list<Block> blocks_;
-  std::forward_list<Block>::iterator last_{blocks_.end()};
+  std::list<Block> blocks_;
   std::size_t bytes_{0};
   bool lastBlockEmpty_{false};
 };
 } // namespace Fortran::parser
 #endif // FORTRAN_PARSER_CHAR_BUFFER_H_

flang/include/flang/Parser/instrumented-parser.h

if (UserState * ustate{state.userState()}) {
       if (ParsingLog * log{ustate->log()}) {
         const char *at{state.GetLocation()};
         if (log->Fails(at, tag_, state)) {
           return std::nullopt;
         }
         Messages messages{std::move(state.messages())};
         std::optional<resultType> result{parser_.Parse(state)};
         log->Note(at, tag_, result.has_value(), state);
-        state.messages().Restore(std::move(messages));
+        state.messages().Annex(std::move(messages));
         return result;
       }
     }
     return parser_.Parse(state);
   }
 
 private:
   const MessageFixedText tag_;

flang/include/flang/Parser/message.h

 #include "char-block.h"
 #include "char-set.h"
 #include "provenance.h"
 #include "flang/Common/idioms.h"
 #include "flang/Common/reference-counted.h"
 #include "flang/Common/restorer.h"
 #include <cstddef>
 #include <cstring>
 #include <forward_list>
+#include <list>
 #include <optional>
 #include <string>
 #include <utility>
 #include <variant>
 
 namespace Fortran::parser {
 
 // Use "..."_err_en_US and "..."_en_US literals to define the static
std::variant<MessageFixedText, MessageFormattedText, MessageExpectedText>
       text_;
   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();
-    }
-  }
+  Messages(Messages &&that) : messages_{std::move(that.messages_)} {}
   Messages &operator=(Messages &&that) {
     messages_ = std::move(that.messages_);
-    if (messages_.empty()) {
-      ResetLastPointer();
-    } else {
-      last_ = that.last_;
-      that.ResetLastPointer();
-    }
     return *this;
   }
 
-  std::forward_list<Message> &messages() { return messages_; }
+  std::list<Message> &messages() { return messages_; }
   bool empty() const { return messages_.empty(); }
-  void clear();
+  void clear() { messages_.clear(); }
 
   template <typename... A> Message &Say(A &&...args) {
-    last_ = messages_.emplace_after(last_, std::forward<A>(args)...);
-    return *last_;
+    return messages_.emplace_back(std::forward<A>(args)...);
   }
 
   void Annex(Messages &&that) {
-    if (!that.messages_.empty()) {
-      messages_.splice_after(last_, that.messages_);
-      last_ = that.last_;
-      that.ResetLastPointer();
-    }
-  }
-
-  void Restore(Messages &&that) {
-    that.Annex(std::move(*this));
-    *this = std::move(that);
+    messages_.splice(messages_.end(), that.messages_);
   }
 
   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(); }
-
-  std::forward_list<Message> messages_;
-  std::forward_list<Message>::iterator last_{messages_.before_begin()};
+  std::list<Message> messages_;
 };
 
 class ContextualMessages {
 public:
   ContextualMessages() = default;
   ContextualMessages(CharBlock at, Messages *m) : at_{at}, messages_{m} {}
   explicit ContextualMessages(Messages *m) : messages_{m} {}
   ContextualMessages(const ContextualMessages &that)

flang/lib/Parser/basic-parsers.h

public:
   using resultType = typename A::resultType;
   constexpr BacktrackingParser(const BacktrackingParser &) = default;
   constexpr BacktrackingParser(const A &parser) : parser_{parser} {}
   std::optional<resultType> Parse(ParseState &state) const {
     Messages messages{std::move(state.messages())};
     ParseState backtrack{state};
     std::optional<resultType> result{parser_.Parse(state)};
     if (result) {
-      state.messages().Restore(std::move(messages));
+      state.messages().Annex(std::move(messages));
     } else {
       state = std::move(backtrack);
       state.messages() = std::move(messages);
     }
     return result;
   }
 
 private:
std::optional<resultType> Parse(ParseState &state) const {
     Messages messages{std::move(state.messages())};
     ParseState backtrack{state};
     std::optional<resultType> result{std::get<0>(ps_).Parse(state)};
     if constexpr (sizeof...(Ps) > 0) {
       if (!result) {
         ParseRest<1>(result, state, backtrack);
       }
     }
-    state.messages().Restore(std::move(messages));
+    state.messages().Annex(std::move(messages));
     return result;
   }
 
 private:
   template <int J>
   void ParseRest(std::optional<resultType> &result, ParseState &state,
       ParseState &backtrack) const {
     ParseState prevState{std::move(state)};
if (!originallyDeferred && state.messages().empty() &&
           state.set_deferMessages(false);
           return ax;
         }
       }
       state = backtrack;
     }
     Messages messages{std::move(state.messages())};
     if (std::optional<resultType> ax{pa_.Parse(state)}) {
-      state.messages().Restore(std::move(messages));
+      state.messages().Annex(std::move(messages));
       return ax;
     }
     messages.Annex(std::move(state.messages()));
     bool hadDeferredMessages{state.anyDeferredMessages()};
     bool anyTokenMatched{state.anyTokenMatched()};
     state = std::move(backtrack);
     state.set_deferMessages(true);
     std::optional<resultType> bx{pb3_.Parse(state)};

flang/lib/Parser/char-buffer.cpp

 #include <cstring>
 
 namespace Fortran::parser {
 
 char *CharBuffer::FreeSpace(std::size_t &n) {
   int offset{LastBlockOffset()};
   if (blocks_.empty()) {
     blocks_.emplace_front();
-    last_ = blocks_.begin();
     lastBlockEmpty_ = true;
   } else if (offset == 0 && !lastBlockEmpty_) {
-    last_ = blocks_.emplace_after(last_);
+    blocks_.emplace_back();
     lastBlockEmpty_ = true;
   }
   n = Block::capacity - offset;
-  return last_->data + offset;
+  return blocks_.back().data + offset;
 }
 
 void CharBuffer::Claim(std::size_t n) {
   if (n > 0) {
     bytes_ += n;
     lastBlockEmpty_ = false;
   }
 }

flang/lib/Parser/message.cpp

return std::visit(
           [](const ProvenanceRange &pr1, const ProvenanceRange &pr2) {
             return pr1.start() == pr2.start();
           },
           [](const auto &, const auto &) { return false; },
       },
       location_, that.location_);
 }
 
-void Messages::clear() {
-  messages_.clear();
-  ResetLastPointer();
-}
-
 bool Messages::Merge(const Message &msg) {
   if (msg.IsMergeable()) {
     for (auto &m : messages_) {
       if (m.Merge(msg)) {
         return true;
       }
     }
   }
   return false;
 }
 
 void Messages::Merge(Messages &&that) {
   if (messages_.empty()) {
     *this = std::move(that);
   } else {
     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_;
+        auto next{that.messages_.begin()};
+        ++next;
+        messages_.splice(
+            messages_.end(), that.messages_, that.messages_.begin(), next);
       }
     }
-    that.ResetLastPointer();
   }
 }
 
 void Messages::Copy(const Messages &that) {
   for (const Message &m : that.messages_) {
     Message copy{m};
     Say(std::move(copy));
   }