[ADT] Fix join_impl using the wrong size when calculating total length

[njames93]

Ping.

[dblaikie]

Any chance of testing this? Could test the 'capacity' after join to check its the right size?

[njames93]

In D83305#2474378, @dblaikie wrote:

Any chance of testing this? Could test the 'capacity' after join to check its the right size?

How do you suppose I do that, maybe expensive checks to get the capacity after reserve and after all items have been added and ensure they are the same, otherwise the string grew during appending.

[dblaikie]

In D83305#2474466, @njames93 wrote:

In D83305#2474378, @dblaikie wrote:

Any chance of testing this? Could test the 'capacity' after join to check its the right size?

How do you suppose I do that, maybe expensive checks to get the capacity after reserve and after all items have been added and ensure they are the same, otherwise the string grew during appending.

Oh, nah, nothing that'd require expensive checks - you could add an assert that size == Len at the end of the function (would have to have some way of avoiding the case for short results that are below the starting capacity, though... perhaps checking if capacity grew over the reserve call, and only asserting in that case)). But I was thinking more along the lines of a unit test that tests join and checks the capacity isn't bigger than the size for a few hardcoded samples.

[njames93]

In D83305#2474470, @dblaikie wrote:

In D83305#2474466, @njames93 wrote:

In D83305#2474378, @dblaikie wrote:

Any chance of testing this? Could test the 'capacity' after join to check its the right size?

How do you suppose I do that, maybe expensive checks to get the capacity after reserve and after all items have been added and ensure they are the same, otherwise the string grew during appending.

Oh, nah, nothing that'd require expensive checks - you could add an assert that size == Len at the end of the function (would have to have some way of avoiding the case for short results that are below the starting capacity, though... perhaps checking if capacity grew over the reserve call, and only asserting in that case)). But I was thinking more along the lines of a unit test that tests join and checks the capacity isn't bigger than the size for a few hardcoded samples.

Oh that assert is fine, the unit test won't be a good test. As we don't control std string, it's capacity for calls to reserve will be implementation defined

[dblaikie]

In D83305#2474484, @njames93 wrote:

In D83305#2474470, @dblaikie wrote:

In D83305#2474466, @njames93 wrote:

In D83305#2474378, @dblaikie wrote:

Any chance of testing this? Could test the 'capacity' after join to check its the right size?

How do you suppose I do that, maybe expensive checks to get the capacity after reserve and after all items have been added and ensure they are the same, otherwise the string grew during appending.

Oh, nah, nothing that'd require expensive checks - you could add an assert that size == Len at the end of the function (would have to have some way of avoiding the case for short results that are below the starting capacity, though... perhaps checking if capacity grew over the reserve call, and only asserting in that case)). But I was thinking more along the lines of a unit test that tests join and checks the capacity isn't bigger than the size for a few hardcoded samples.

Oh that assert is fine, the unit test won't be a good test. As we don't control std string, it's capacity for calls to reserve will be implementation defined

The spec seems to be a bit more precise than that (using cppreference, which isn't authoritative, but more readable): "If new_cap is greater than the current capacity(), new storage is allocated, and capacity() is made equal or greater than new_cap."

So a unit test that joins some large strings (if it wanted to be fancy, it could even generate a string intentionally larger than std::string's default capacity, whatever it happens to be) and if the resulting string has a larger capacity than std::string's default capacity, verify that the capacity is exactly equal to the string length.

[njames93]

In D83305#2474497, @dblaikie wrote:

The spec seems to be a bit more precise than that (using cppreference, which isn't authoritative, but more readable): "If new_cap is greater than the current capacity(), new storage is allocated, and capacity() is made equal or greater than new_cap."

So a unit test that joins some large strings (if it wanted to be fancy, it could even generate a string intentionally larger than std::string's default capacity, whatever it happens to be) and if the resulting string has a larger capacity than std::string's default capacity, verify that the capacity is exactly equal to the string length.

That still sounds like it'll cause some issues. The main thing we want to test (which is the purpose of this patch) is that the string didn't grow while we are appending all the pieces. It's impossible to tell externally if that happened as reserve may choose to over allocate.
Putting an assert in the function that the capacity before hasn't changed should be more than enough, WDYT?

[njames93]

Add assert to enusre correct behaviour.

[dblaikie]

Sounds good - thanks!

llvm/include/llvm/ADT/StringExtras.h

 inline std::string join_impl(IteratorT Begin, IteratorT End,
                              StringRef Separator, std::forward_iterator_tag) {
   std::string S;
   if (Begin == End)
     return S;
 
   size_t Len = (std::distance(Begin, End) - 1) * Separator.size();
   for (IteratorT I = Begin; I != End; ++I)
-    Len += (*Begin).size();
+    Len += I->size();
   S.reserve(Len);
+  size_t PrevCapacity = S.capacity();
+  (void)PrevCapacity;
   S += (*Begin);
   while (++Begin != End) {
     S += Separator;
     S += (*Begin);
   }
+  assert(PrevCapacity == S.capacity() && "String grew during building");
   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,