[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

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+")

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

 //===-- GDBRemoteCommunicationServerLLGS.cpp ------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include <cerrno>
 
 #include "lldb/Host/Config.h"
 
 
 #include <chrono>
 #include <cstring>
 #include <limits>
 #include <thread>
 
 #include "GDBRemoteCommunicationServerLLGS.h"
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

 //===-- ProcessGDBRemote.cpp ----------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Host/Config.h"
 
 #include <cerrno>
 #include <cstdlib>
 #if LLDB_ENABLE_POSIX
 #include <netinet/in.h>
 #include <sys/mman.h>
 #include <sys/socket.h>
 #include <unistd.h>
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 : 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/lib/IR/DataLayout.cpp

Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) {
   return Layout;
 }
 
 static Error reportError(const Twine &Message) {
   return createStringError(inconvertibleErrorCode(), Message);
 }
 
 /// Checked version of split, to ensure mandatory subparts.
-static Error split(StringRef Str, char Separator,
+static Error dataLayoutSplit(StringRef Str, char Separator,
                              std::pair<StringRef, StringRef> &Split) {
   assert(!Str.empty() && "parse error, string can't be empty here");
   Split = Str.split(Separator);
   if (Split.second.empty() && Split.first != Str)
     return reportError("Trailing separator in datalayout string");
   if (!Split.second.empty() && Split.first.empty())
     return reportError("Expected token before separator in datalayout string");
   return Error::success();
 }
static Error getAddrSpace(StringRef R, unsigned &AddrSpace) {
   return Error::success();
 }
 
 Error DataLayout::parseSpecifier(StringRef Desc) {
   StringRepresentation = std::string(Desc);
   while (!Desc.empty()) {
     // Split at '-'.
     std::pair<StringRef, StringRef> Split;
-    if (Error Err = split(Desc, '-', Split))
+    if (Error Err = dataLayoutSplit(Desc, '-', Split))
       return Err;
     Desc = Split.second;
 
     // Split at ':'.
-    if (Error Err = split(Split.first, ':', Split))
+    if (Error Err = dataLayoutSplit(Split.first, ':', Split))
       return Err;
 
     // Aliases used below.
     StringRef &Tok  = Split.first;  // Current token.
     StringRef &Rest = Split.second; // The rest of the string.
 
     if (Tok == "ni") {
       do {
-        if (Error Err = split(Rest, ':', Split))
+        if (Error Err = dataLayoutSplit(Rest, ':', Split))
           return Err;
         Rest = Split.second;
         unsigned AS;
         if (Error Err = getInt(Split.first, AS))
           return Err;
         if (AS == 0)
           return reportError("Address space 0 can never be non-integral");
         NonIntegralAddressSpaces.push_back(AS);
case 'p': {
           return Err;
       if (!isUInt<24>(AddrSpace))
         return reportError("Invalid address space, must be a 24bit integer");
 
       // Size.
       if (Rest.empty())
         return reportError(
             "Missing size specification for pointer in datalayout string");
-      if (Error Err = split(Rest, ':', Split))
+      if (Error Err = dataLayoutSplit(Rest, ':', Split))
         return Err;
       unsigned PointerMemSize;
       if (Error Err = getIntInBytes(Tok, PointerMemSize))
         return Err;
       if (!PointerMemSize)
         return reportError("Invalid pointer size of 0 bytes");
 
       // ABI alignment.
       if (Rest.empty())
         return reportError(
             "Missing alignment specification for pointer in datalayout string");
-      if (Error Err = split(Rest, ':', Split))
+      if (Error Err = dataLayoutSplit(Rest, ':', Split))
         return Err;
       unsigned PointerABIAlign;
       if (Error Err = getIntInBytes(Tok, PointerABIAlign))
         return Err;
       if (!isPowerOf2_64(PointerABIAlign))
         return reportError("Pointer ABI alignment must be a power of 2");
 
       // Size of index used in GEP for address calculation.
       // The parameter is optional. By default it is equal to size of pointer.
       unsigned IndexSize = PointerMemSize;
 
       // Preferred alignment.
       unsigned PointerPrefAlign = PointerABIAlign;
       if (!Rest.empty()) {
-        if (Error Err = split(Rest, ':', Split))
+        if (Error Err = dataLayoutSplit(Rest, ':', Split))
           return Err;
         if (Error Err = getIntInBytes(Tok, PointerPrefAlign))
           return Err;
         if (!isPowerOf2_64(PointerPrefAlign))
           return reportError(
               "Pointer preferred alignment must be a power of 2");
 
         // Now read the index. It is the second optional parameter here.
         if (!Rest.empty()) {
-          if (Error Err = split(Rest, ':', Split))
+          if (Error Err = dataLayoutSplit(Rest, ':', Split))
             return Err;
           if (Error Err = getIntInBytes(Tok, IndexSize))
             return Err;
           if (!IndexSize)
             return reportError("Invalid index size of 0 bytes");
         }
       }
       if (Error Err = setPointerAlignment(
case 'a': {
       if (AlignType == AGGREGATE_ALIGN && Size != 0)
         return reportError(
             "Sized aggregate specification in datalayout string");
 
       // ABI alignment.
       if (Rest.empty())
         return reportError(
             "Missing alignment specification in datalayout string");
-      if (Error Err = split(Rest, ':', Split))
+      if (Error Err = dataLayoutSplit(Rest, ':', Split))
         return Err;
       unsigned ABIAlign;
       if (Error Err = getIntInBytes(Tok, ABIAlign))
         return Err;
       if (AlignType != AGGREGATE_ALIGN && !ABIAlign)
         return reportError(
             "ABI alignment specification must be >0 for non-aggregate types");
 
       if (!isUInt<16>(ABIAlign))
         return reportError("Invalid ABI alignment, must be a 16bit integer");
       if (ABIAlign != 0 && !isPowerOf2_64(ABIAlign))
         return reportError("Invalid ABI alignment, must be a power of 2");
 
       // Preferred alignment.
       unsigned PrefAlign = ABIAlign;
       if (!Rest.empty()) {
-        if (Error Err = split(Rest, ':', Split))
+        if (Error Err = dataLayoutSplit(Rest, ':', Split))
           return Err;
         if (Error Err = getIntInBytes(Tok, PrefAlign))
           return Err;
       }
 
       if (!isUInt<16>(PrefAlign))
         return reportError(
             "Invalid preferred alignment, must be a 16bit integer");
case 'n':  // Native integer types.
         if (Error Err = getInt(Tok, Width))
           return Err;
         if (Width == 0)
           return reportError(
               "Zero width native integer type in datalayout string");
         LegalIntWidths.push_back(Width);
         if (Rest.empty())
           break;
-        if (Error Err = split(Rest, ':', Split))
+        if (Error Err = dataLayoutSplit(Rest, ':', Split))
           return Err;
       }
       break;
     case 'S': { // Stack natural alignment.
       uint64_t Alignment;
       if (Error Err = getIntInBytes(Tok, Alignment))
         return Err;
       if (Alignment != 0 && !llvm::isPowerOf2_64(Alignment))

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);
+}