Add StringExtras join_items function

[zturner]

Summary

There's already llvm::join which is useful for joining a container of items. But there is no way to join items of disparate types, or types who are not in a container for whatever reason.

For example, if you have a std::string, a llvm::StringRef, and a const char *, you would have to manually construct a container to put them in before joining them, which is inconvnient.

This adds a variadic join_items function for this purpose.

[zturner]

Added missing unit test file.

[zturner]

Trying this again, for some reason StringExtrasTest.cpp isn't uploading.

[zturner]

Added some tests to show that it works when you use operands of different types.

Also templatized the separator so that it can be a char (or anything else for that matter), and not just a StringRef.

[zturner]

Ping. Anyone have objections?

[sanjoy]

Looks fine to me, but I don't grok the intricacies of std::forward and variadic templates well enough to review this. Perhaps @majnemer or @dblaikie can chime in?

[mehdi_amini]

How does it compare to Twine in practice?

[zturner]

In D24880#553442, @mehdi_amini wrote:

How does it compare to Twine in practice?

I don't think it solves the same problem as a Twine. While twines are good for concatenating values as you descend into a call hierarchy, it doesn't work when you want to build a concatenation of the results of many different function return values and then use that -- perhaps multiple times -- in one function.

[mehdi_amini]

What about: `auto Result = (Twine(foo()) + bar() + baz()).str()`?

[zturner]

In D24880#553444, @mehdi_amini wrote:

What about: `auto Result = (Twine(foo()) + bar() + baz()).str()`?

Hadn't thought of that, but that also doesn't work of foo(), bar(), and baz() are of type const char *. In that case you need to invoke operator += on the std::string

[zturner]

Also I feel like Twine(foo() + '/' bar() + '/' + baz()).str() is a big more difficult to visually grok than llvm::join_items('/', foo(), bar(), baz());

[mehdi_amini]

In D24880#553448, @zturner wrote:

In D24880#553444, @mehdi_amini wrote:

What about: `auto Result = (Twine(foo()) + bar() + baz()).str()`?

Hadn't thought of that, but that also doesn't work of foo(), bar(), and baz() are of type const char *. In that case you need to invoke operator += on the std::string

No: the twine capture the pointers, and create a string *at the end only* (the call to str()). That said it is not terribly efficient: it'll stream to a SmallVector and copy the result to the string. (You can instead create a small vector and supply it to Twine::toVector() to save a copy).
Anyway...

Also I feel like Twine(foo() + '/' bar() + '/' + baz()).str() is a big more difficult to visually grok than llvm::join_items('/', foo(), bar(), baz());

Right, I agree with that.

include/llvm/ADT/StringExtras.h

222 ↗

(On Diff #72340)

Could you add a "reserve" stage here?

[zturner]

include/llvm/ADT/StringExtras.h

222 ↗

(On Diff #72340)

Seems reasonable, but how big? (max(1, sizeof...(Items)) - 1) * Separator.size()) is a lower bound. Should I just go with that?

[mehdi_amini]

include/llvm/ADT/StringExtras.h

222 ↗

(On Diff #72340)

I'd have a variadic template (with some overload) that sum the length of each elements. So that the exact length is computed. This is what join_impl is doing iteratively I believe.

[zturner]

Updated to compute the length before doing the concatenation.

[mehdi_amini]

include/llvm/ADT/StringExtras.h

246 ↗

(On Diff #72663)

Isn't there a missing + 1 for the trailing '\0' ?

[zturner]

include/llvm/ADT/StringExtras.h

246 ↗

(On Diff #72663)

Good catch. I'll fix that locally, not worth uploading a new patch for though.

[mehdi_amini]

LGTM.

include/llvm/ADT/StringExtras.h

226 ↗

(On Diff #72663)

Do you need the B in this function?

[zturner]

include/llvm/ADT/StringExtras.h

226 ↗

(On Diff #72663)

My understanding is that it is needed to disambiguate the two overloads. If you have these two:

template <typename A1>
size_t join_items_size(const A1 &A) {
}

template<typename A1, typename... As>
size_t join_items_size(const A1 &A, As &&... Items) {
}

Then if you call it as:

size_t x = join_items_size("Test");

it will be ambiguous, because the second overload could have a parameter pack of size 0. Correct me if I'm wrong though, I admit I am not an expert here :)

llvm/trunk/include/llvm/ADT/StringExtras.h

default:
     }
   }
 }
 
 /// PrintEscapedString - Print each character of the specified string, escaping
 /// it if it is not printable or if it is an escape char.
 void PrintEscapedString(StringRef Name, raw_ostream &Out);
 
+namespace detail {
+
 template <typename IteratorT>
 inline std::string join_impl(IteratorT Begin, IteratorT End,
                              StringRef Separator, std::input_iterator_tag) {
   std::string S;
   if (Begin == End)
     return S;
 
   S += (*Begin);
inline std::string join_impl(IteratorT Begin, IteratorT End,
   S += (*Begin);
   while (++Begin != End) {
     S += Separator;
     S += (*Begin);
   }
   return S;
 }
 
+template <typename Sep>
+inline void join_items_impl(std::string &Result, Sep Separator) {}
+
+template <typename Sep, typename Arg>
+inline void join_items_impl(std::string &Result, Sep Separator,
+                            const Arg &Item) {
+  Result += Item;
+}
+
+template <typename Sep, typename Arg1, typename... Args>
+inline void join_items_impl(std::string &Result, Sep Separator, const Arg1 &A1,
+                            Args &&... Items) {
+  Result += A1;
+  Result += Separator;
+  join_items_impl(Result, Separator, std::forward<Args>(Items)...);
+}
+
+inline size_t join_one_item_size(char C) { return 1; }
+inline size_t join_one_item_size(const char *S) { return S ? ::strlen(S) : 0; }
+
+template <typename T> inline size_t join_one_item_size(const T &Str) {
+  return Str.size();
+}
+
+inline size_t join_items_size() { return 0; }
+
+template <typename A1> inline size_t join_items_size(const A1 &A) {
+  return join_one_item_size(A);
+}
+template <typename A1, typename... Args>
+inline size_t join_items_size(const A1 &A, Args &&... Items) {
+  return join_one_item_size(A) + join_items_size(std::forward<Args>(Items)...);
+}
+}
+
 /// Joins the strings in the range [Begin, End), adding Separator between
 /// the elements.
 template <typename IteratorT>
 inline std::string join(IteratorT Begin, IteratorT End, StringRef Separator) {
   typedef typename std::iterator_traits<IteratorT>::iterator_category tag;
-  return join_impl(Begin, End, Separator, tag());
+  return detail::join_impl(Begin, End, Separator, tag());
+}
+
+/// Joins the strings in the parameter pack \p Items, adding \p Separator
+/// between the elements.  All arguments must be implicitly convertible to
+/// std::string, or there should be an overload of std::string::operator+=()
+/// that accepts the argument explicitly.
+template <typename Sep, typename... Args>
+inline std::string join_items(Sep Separator, Args &&... Items) {
+  std::string Result;
+  if (sizeof...(Items) == 0)
+    return Result;
+
+  size_t NS = detail::join_one_item_size(Separator);
+  size_t NI = detail::join_items_size(std::forward<Args>(Items)...);
+  Result.reserve(NI + (sizeof...(Items) - 1) * NS + 1);
+  detail::join_items_impl(Result, Separator, std::forward<Args>(Items)...);
+  return Result;
 }
 
 } // End llvm namespace
 
 #endif

llvm/trunk/unittests/ADT/CMakeLists.txt

set(ADTSources
   SetVectorTest.cpp
   SimpleIListTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
+  StringExtrasTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
   VariadicFunctionTest.cpp
  )
 
 add_llvm_unittest(ADTTests
   ${ADTSources}
   )
 
 add_dependencies(ADTTests intrinsics_gen)

llvm/trunk/unittests/ADT/StringExtrasTest.cpp

+//===- StringExtrasTest.cpp - Unit tests for String extras ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringExtras.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(StringExtrasTest, Join) {
+  std::vector<std::string> Items;
+  EXPECT_EQ("", join(Items.begin(), Items.end(), " <sep> "));
+
+  Items = {"foo"};
+  EXPECT_EQ("foo", join(Items.begin(), Items.end(), " <sep> "));
+
+  Items = {"foo", "bar"};
+  EXPECT_EQ("foo <sep> bar", join(Items.begin(), Items.end(), " <sep> "));
+
+  Items = {"foo", "bar", "baz"};
+  EXPECT_EQ("foo <sep> bar <sep> baz",
+            join(Items.begin(), Items.end(), " <sep> "));
+}
+
+TEST(StringExtrasTest, JoinItems) {
+  const char *Foo = "foo";
+  std::string Bar = "bar";
+  llvm::StringRef Baz = "baz";
+  char X = 'x';
+
+  EXPECT_EQ("", join_items(" <sep> "));
+  EXPECT_EQ("", join_items('/'));
+
+  EXPECT_EQ("foo", join_items(" <sep> ", Foo));
+  EXPECT_EQ("foo", join_items('/', Foo));
+
+  EXPECT_EQ("foo <sep> bar", join_items(" <sep> ", Foo, Bar));
+  EXPECT_EQ("foo/bar", join_items('/', Foo, Bar));
+
+  EXPECT_EQ("foo <sep> bar <sep> baz", join_items(" <sep> ", Foo, Bar, Baz));
+  EXPECT_EQ("foo/bar/baz", join_items('/', Foo, Bar, Baz));
+
+  EXPECT_EQ("foo <sep> bar <sep> baz <sep> x",
+            join_items(" <sep> ", Foo, Bar, Baz, X));
+
+  EXPECT_EQ("foo/bar/baz/x", join_items('/', Foo, Bar, Baz, X));
+}