[llvm] [ADT] Add a range/iterator-based Split()

[mgorny]

Summary

Add a llvm::Split() implementation that can be used via range-for loop,
e.g.:

for (StringRef x : llvm::Split("foo,bar,baz", ','))
  ...

The implementation uses an additional SplittingIterator class that
uses StringRef::split() internally.

[mgorny]

llvm/lib/IR/DataLayout.cpp

219 ↗

(On Diff #375093)

I needed to rename this due to collision with llvm::split class.

[mgorny]

Convert more LLDB gdb-remote calls.

[lattner]

This is really nice! Please fix the clang-tidy casing issues, but otherwise LGTM!

[mgorny]

Attempt to fix linter issues.

[labath]

I like it as well :)

llvm/include/llvm/ADT/StringExtras.h

519

This compares the contents of the StringRefs, while it should be comparing the pointers instead. I don't think it can cause correctness issues though I think it might be able to cause super-linear iteration complexity for some pathological inputs and more complex algorithms (a string consisting of many identical substrings, and an algorithm which compares two successive iterators).

Since comparing iterators from different sequences is UB, I think that comparing just Current.data() could actually suffice (the rest could be asserts) -- one has to be careful how he initializes the past-the-end iterator though.

527–529

std::tie(Current, Next) = ...

545–558

Could this be a function that returns iterator_range<SplittingIterator> ?
(I suppose lifetimes could be an issue, but it's not clear to me if that's the case here)

[mgorny]

Filed D110535 for suggested changes.

llvm/include/llvm/ADT/StringExtras.h

527–529

Damnit, I swear it didn't work before! Complained about this pointer something.

lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp

void GDBRemoteCommunicationClient::GetRemoteQSupported() {
 
   StringExtractorGDBRemote response;
   if (SendPacketAndWaitForResponse(packet.GetString(), response) ==
       PacketResult::Success) {
     // Hang on to the qSupported packet, so that platforms can do custom
     // configuration of the transport before attaching/launching the process.
     m_qSupported_response = response.GetStringRef().str();
 
-    llvm::SmallVector<llvm::StringRef, 16> server_features;
-    response.GetStringRef().split(server_features, ';');
-
-    for (llvm::StringRef x : server_features) {
+    for (llvm::StringRef x : llvm::Split(response.GetStringRef(), ';')) {
       if (x == "qXfer:auxv:read+")
         m_supports_qXfer_auxv_read = eLazyBoolYes;
       else if (x == "qXfer:libraries-svr4:read+")
         m_supports_qXfer_libraries_svr4_read = eLazyBoolYes;
       else if (x == "augmented-libraries-svr4-read") {
         m_supports_qXfer_libraries_svr4_read = eLazyBoolYes; // implied
         m_supports_augmented_libraries_svr4_read = eLazyBoolYes;
       } else if (x == "qXfer:libraries:read+")
if (SendPacketAndWaitForResponse(packet, response) ==
           }
         } else if (name.equals("error")) {
           StringExtractorGDBRemote error_extractor(value);
           std::string error_string;
           // Now convert the HEX bytes into a string value
           error_extractor.GetHexByteString(error_string);
           error.SetErrorString(error_string.c_str());
         } else if (name.equals("dirty-pages")) {
-          llvm::SmallVector<llvm::StringRef, 16> split_value;
           std::vector<addr_t> dirty_page_list;
-          value.split(split_value, ',');
-          for (llvm::StringRef x : split_value) {
+          for (llvm::StringRef x : llvm::Split(value, ',')) {
             addr_t page;
             x.consume_front("0x");
             if (llvm::to_integer(x, page, 16))
               dirty_page_list.push_back(page);
           }
           region_info.SetDirtyPageList(dirty_page_list);
         }
       }

lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationServerLLGS.cpp

if (!m_current_process ||
       (m_current_process->GetID() == LLDB_INVALID_PROCESS_ID))
     return SendErrorResponse(Status("Process not running."));
 
   std::string path_hint;
 
   StringRef packet_str{packet.GetStringRef()};
   assert(packet_str.startswith("qSaveCore"));
   if (packet_str.consume_front("qSaveCore;")) {
-    llvm::SmallVector<llvm::StringRef, 2> fields;
-    packet_str.split(fields, ';');
-
-    for (auto x : fields) {
+    for (auto x : llvm::Split(packet_str, ';')) {
       if (x.consume_front("path-hint:"))
         StringExtractor(x).GetHexByteString(path_hint);
       else
         return SendErrorResponse(Status("Unsupported qSaveCore option"));
     }
   }
 
   llvm::Expected<std::string> ret = m_current_process->SaveCore(path_hint);

lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp

bool ProcessGDBRemote::ParsePythonTargetDefinition(
   }
   return false;
 }
 
 static size_t SplitCommaSeparatedRegisterNumberString(
     const llvm::StringRef &comma_separated_register_numbers,
     std::vector<uint32_t> &regnums, int base) {
   regnums.clear();
-  llvm::SmallVector<llvm::StringRef, 4> split_string;
-  comma_separated_register_numbers.split(split_string, ',');
-  for (llvm::StringRef x : split_string) {
+  for (llvm::StringRef x : llvm::Split(comma_separated_register_numbers, ',')) {
     uint32_t reg;
     if (llvm::to_integer(x, reg, base))
       regnums.push_back(reg);
   }
   return regnums.size();
 }
 
 void ProcessGDBRemote::BuildDynamicRegisterInfo(bool force) {
size_t ProcessGDBRemote::UpdateThreadIDsFromStopReplyThreadsValue(
   } while (thread_ids.GetChar() == ',');
 
   return m_thread_ids.size();
 }
 
 size_t ProcessGDBRemote::UpdateThreadPCsFromStopReplyThreadsValue(
     llvm::StringRef value) {
   m_thread_pcs.clear();
-  llvm::SmallVector<llvm::StringRef, 16> split_value;
-  value.split(split_value, ',');
-  for (llvm::StringRef x : split_value) {
+  for (llvm::StringRef x : llvm::Split(value, ',')) {
     lldb::addr_t pc;
     if (llvm::to_integer(x, pc, 16))
       m_thread_pcs.push_back(pc);
   }
   return m_thread_pcs.size();
 }
 
 bool ProcessGDBRemote::UpdateThreadIDList() {
if (m_gdb_comm.SendPacketAndWaitForResponse(packet.GetString(), response) ==
     if (response.IsErrorResponse())
       return llvm::createStringError(
           llvm::inconvertibleErrorCode(),
           llvm::formatv("qSaveCore returned an error"));
 
     std::string path;
 
     // process the response
-    llvm::SmallVector<llvm::StringRef, 1> reply_data;
-    response.GetStringRef().split(reply_data, ';');
-    for (auto x : reply_data) {
+    for (auto x : llvm::Split(response.GetStringRef(), ';')) {
       if (x.consume_front("core-path:"))
         StringExtractor(x).GetHexByteString(path);
     }
 
     // verify that we've gotten what we need
     if (path.empty())
       return llvm::createStringError(llvm::inconvertibleErrorCode(),
                                      "qSaveCore returned no core path");

llvm/include/llvm/ADT/StringExtras.h

operator StringRef() {
     if (First) {
       First = false;
       return {};
     }
     return Separator;
   }
 };
 
+/// A forward iterator over partitions of string over a separator.
+class SplittingIterator
+    : public iterator_facade_base<SplittingIterator, std::forward_iterator_tag,
+                                  StringRef> {
+  StringRef Current;
+  StringRef Next;
+  StringRef Separator;
+
+public:
+  SplittingIterator(StringRef Str, StringRef Separator)
+      : Next(Str), Separator(Separator) {
+    ++*this;
+  }
+
+  bool operator==(const SplittingIterator &R) const {
+    return Current == R.Current && Next == R.Next && Separator == R.Separator;
+  }
+
+  const StringRef &operator*() const { return Current; }
+
+  StringRef &operator*() { return Current; }
+
+  SplittingIterator &operator++() {
+    std::pair<StringRef, StringRef> Res = Next.split(Separator);
+    Current = Res.first;
+    Next = Res.second;
+    return *this;
+  }
+};
+
+/// Split the specified string over a separator and return a range-compatible
+/// iterable over its partitions.  Used to permit conveniently iterating
+/// over separated strings like so:
+///
+/// \code
+///   for (StringRef x : llvm::Split("foo,bar,baz", ','))
+///     ...;
+/// \end
+///
+/// Note that the passed string must remain valid throuhgout lifetime
+/// of the iterators.
+class Split {
+  StringRef Str;
+  std::string SeparatorStr;
+
+public:
+  Split(StringRef NewStr, StringRef Separator)
+      : Str(NewStr), SeparatorStr(Separator) {}
+  Split(StringRef NewStr, char Separator)
+      : Str(NewStr), SeparatorStr(1, Separator) {}
+
+  SplittingIterator begin() { return SplittingIterator(Str, SeparatorStr); }
+
+  SplittingIterator end() { return SplittingIterator("", SeparatorStr); }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_STRINGEXTRAS_H

llvm/unittests/ADT/StringExtrasTest.cpp

TEST(StringExtrasTest, toStringAPSInt) {
   EXPECT_EQ(toString(APSInt(APInt(8, 255), isUnsigned), 16), "FF");
 
   isUnsigned = false;
   EXPECT_EQ(toString(APSInt(APInt(8, 255), isUnsigned), 2), "-1");
   EXPECT_EQ(toString(APSInt(APInt(8, 255), isUnsigned), 8), "-1");
   EXPECT_EQ(toString(APSInt(APInt(8, 255), isUnsigned), 10), "-1");
   EXPECT_EQ(toString(APSInt(APInt(8, 255), isUnsigned), 16), "-1");
 }
+
+TEST(StringExtrasTest, splitStringRef) {
+  auto Spl = Split("foo<=>bar<=><=>baz", "<=>");
+  auto It = Spl.begin();
+  auto End = Spl.end();
+
+  ASSERT_NE(It, End);
+  EXPECT_EQ(*It, StringRef("foo"));
+  ASSERT_NE(++It, End);
+  EXPECT_EQ(*It, StringRef("bar"));
+  ASSERT_NE(++It, End);
+  EXPECT_EQ(*It, StringRef(""));
+  ASSERT_NE(++It, End);
+  EXPECT_EQ(*It, StringRef("baz"));
+  ASSERT_EQ(++It, End);
+}
+
+TEST(StringExtrasTest, splItChar) {
+  auto Spl = Split("foo,bar,,baz", ',');
+  auto It = Spl.begin();
+  auto End = Spl.end();
+
+  ASSERT_NE(It, End);
+  EXPECT_EQ(*It, StringRef("foo"));
+  ASSERT_NE(++It, End);
+  EXPECT_EQ(*It, StringRef("bar"));
+  ASSERT_NE(++It, End);
+  EXPECT_EQ(*It, StringRef(""));
+  ASSERT_NE(++It, End);
+  EXPECT_EQ(*It, StringRef("baz"));
+  ASSERT_EQ(++It, End);
+}