From 764261c12ab059cd15607a1c2d2a7ff015dfe7ce Mon Sep 17 00:00:00 2001
From: Nicholas Ormrod <njormrod@fb.com>
Date: Mon, 24 Feb 2014 10:40:39 -0800
Subject: [PATCH] Remove disallowed &* of FwdIterator

Summary:
Iterators are not required to dereference into lvalues, so
taking the address of the dereferenced value of a general iterator
may cause a compile-time error.

This bug was observed when compiling clang-3.4. Clang uses a custom
iterator type when calling fbstring::replace, whose dereference operator
returns a char (instead of the 'expected' const char&).

FBString takes the address of the dereference in order to test if the
iterator is actually an iterator referencing its own data. This protects
the string from data trampling in certain cases. See the added test case
for an example.

For sequence containers, the standard specifies that supplying interal
iterators for such operations is forbidden. The standard also states
that the iterators passed into containers will be dereferenced at each
location exactly once. The standard (from by too-brief inspection) does
not specify either of these restrictions for strings, which I find odd.

As a compromise between safety and strict compliance, the offending code
is now only run when the iterator type is either fbstring::iterator or
fbstring::const_iterator. In these cases, we know that it is safe to
both dereference the iterator multiple times and to take its
dereference's address.

While fixing this error, I noticed that fbstring::replaceImpl was
public. It is now private.

Test Plan:
Added a new test case to FBStringTest.cpp.

fbconfig -r folly && fbmake opt && fbmake runtests_opt

Reviewed By: delong.j@fb.com

FB internal diff: D1185655
---
 folly/FBString.h            | 13 +++++++------
 folly/test/FBStringTest.cpp | 17 +++++++++++++++++
 2 files changed, 24 insertions(+), 6 deletions(-)

diff --git a/folly/FBString.h b/folly/FBString.h
index 30fcb4ab..d67c075d 100644
--- a/folly/FBString.h
+++ b/folly/FBString.h
@@ -156,7 +156,6 @@ OutIt copy_n(InIt b,
              typename std::iterator_traits<InIt>::difference_type n,
              OutIt d) {
   for (; n != 0; --n, ++b, ++d) {
-    assert((const void*)&*d != &*b);
     *d = *b;
   }
   return d;
@@ -1696,15 +1695,15 @@ private:
   }
 
 private:
-  template <class FwdIterator, class P>
+  template <class FwdIterator>
   bool replaceAliased(iterator i1, iterator i2,
-                      FwdIterator s1, FwdIterator s2, P*) {
+                      FwdIterator s1, FwdIterator s2, std::false_type) {
     return false;
   }
 
   template <class FwdIterator>
   bool replaceAliased(iterator i1, iterator i2,
-                      FwdIterator s1, FwdIterator s2, value_type*) {
+                      FwdIterator s1, FwdIterator s2, std::true_type) {
     static const std::less_equal<const value_type*> le =
       std::less_equal<const value_type*>();
     const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
@@ -1719,7 +1718,6 @@ private:
     return true;
   }
 
-public:
   template <class FwdIterator>
   void replaceImpl(iterator i1, iterator i2,
                    FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
@@ -1727,7 +1725,10 @@ public:
     (void) checker;
 
     // Handle aliased replace
-    if (replaceAliased(i1, i2, s1, s2, &*s1)) {
+    if (replaceAliased(i1, i2, s1, s2,
+          std::integral_constant<bool,
+            std::is_same<FwdIterator, iterator>::value ||
+            std::is_same<FwdIterator, const_iterator>::value>())) {
       return;
     }
 
diff --git a/folly/test/FBStringTest.cpp b/folly/test/FBStringTest.cpp
index 02aaf449..89613635 100644
--- a/folly/test/FBStringTest.cpp
+++ b/folly/test/FBStringTest.cpp
@@ -1207,6 +1207,23 @@ TEST(FBString, iomanip) {
   ss.str("");
 }
 
+TEST(FBString, rvalueIterators) {
+  // you cannot take &* of a move-iterator, so use that for testing
+  fbstring s = "base";
+  fbstring r = "hello";
+  r.replace(r.begin(), r.end(),
+      make_move_iterator(s.begin()), make_move_iterator(s.end()));
+  EXPECT_EQ("base", r);
+
+  // The following test is probably not required by the standard.
+  // i.e. this could be in the realm of undefined behavior.
+  fbstring b = "123abcXYZ";
+  auto ait = b.begin() + 3;
+  auto Xit = b.begin() + 6;
+  b.replace(ait, b.end(), b.begin(), Xit);
+  EXPECT_EQ("123123abc", b); // if things go wrong, you'd get "123123123"
+}
+
 int main(int argc, char** argv) {
   testing::InitGoogleTest(&argc, argv);
   google::ParseCommandLineFlags(&argc, &argv, true);
-- 
2.34.1