facebook / facebook/folly

fbstring does not handle append/insert with aliasing iterators

Open
#1,679 1 comment 1 reaction 0 assignees View on GitHub
Dominant language
C++
Stars
30.5k
Forks
5.9k
PR merge metrics
No merged PRs in 30d

Description

I'm using an older `folly` version and haven't tried reproducing this for latest, but looking at the latest code for it it looks like the same issue still exists, so reporting this here.

I believe `fbstring::append()` and `fbstring::insert()` do not work correctly for the iterator-based overloads, if the given iterators point to _within_ the `fbstring` being modified.

This is technically legal per the C++ spec, and must behave as if a temporary string were created from the given iterators and _then_ appended/inserted into the mutating string, to avoid overlap/aliasing issues. In fact in `gcc`'s `libstdc++` `std::string` this is exactly what occurs - it creates a temporary string before appending/inserting it into `*this`.

I realize the performance overhead to fix this niche corner-case is likely not worth it, but currently `docs/FBString.md` states `fbstring` is "100% compatible with std::string." So it might be preferable to just point out the issue there in that doc, instead of fixing it.

To test this, add the following to `test/FBStringTest.cpp`:
```
template
void clause11_21_4_6_4_b(String&) {
// this is 11 chars, so that 2 are still in SSO, but 3 are not
const String orig = "smallSTRING";

// this passes because the iterators point outside the changing string
{
String str;
for (int i = 0; i < 3; ++i) {
str.insert(str.begin(), orig.begin(), orig.end());
}
EXPECT_EQ(str, "smallSTRINGsmallSTRINGsmallSTRING") << "Actual: " << str;
}
{
String str;
for (int i = 0; i < 3; ++i) {
str.insert(str.end(), orig.begin(), orig.end());
}
EXPECT_EQ(str, "smallSTRINGsmallSTRINGsmallSTRING") << "Actual: " << str;
}
// this passes because no reallocation occurs
{
String str = orig;
str.insert(str.begin(), str.begin(), str.begin() + orig.size());
EXPECT_EQ(str, "smallSTRINGsmallSTRING") << "Actual: " << str;
}
{
String str = orig;
str.insert(str.end(), str.begin(), str.begin() + orig.size());
EXPECT_EQ(str, "smallSTRINGsmallSTRING") << "Actual: " << str;
}
// this fails because it reallocs, but the iterators point inside the string
{
String str = orig;
for (int i = 0; i < 2; ++i) {
str.insert(str.begin(), str.begin(), str.begin() + orig.size());
}
EXPECT_EQ(str, "smallSTRINGsmallSTRINGsmallSTRING") << "Actual: " << str;
}
{
String str = orig;
for (int i = 0; i < 2; ++i) {
str.insert(str.end(), str.begin(), str.begin() + orig.size());
}
EXPECT_EQ(str, "smallSTRINGsmallSTRINGsmallSTRING") << "Actual: " << str;
}
}
```

And of course this later in that file:
```
TEST_CLAUSE(21_4_6_4_b);
```

Contributor guide

Open the contributing guide

Research direction

Start with the reproducer and TEST_CLAUSE entry in test/FBStringTest.cpp, then inspect the append() and insert() iterator overloads implicated by the report. Review docs/FBString.md for the compatibility claim. Done means the aliasing cases behave like std::string, or the documented compatibility limitation is updated instead, according to the chosen resolution.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.