From bf188b34715fbcd67abc29ab67296ef66567cd44 Mon Sep 17 00:00:00 2001
From: Nicholas Ormrod <njormrod@fb.com>
Date: Fri, 10 Aug 2012 14:04:43 -0700
Subject: [PATCH] Increased std::vector compatibility of fbvector

Summary:
fbvector was not accepting move_iterators for
InputIterator-templated construct, assign, and insert. The root cause
was the check '(b_ <= &*first && &*first < e_)', used to check if the
assignment was from internal data. This addressof check does not compile
with rvalue-references, and causes the first iterator to be dereferenced
more than once; both against the contract of std::vector. The standard
allows for undefined behaviour in the self-iterator case, so there are
no contractual barriers to removing this check.

Test Plan:
run fbvector test and benchmark. An fbgs for 'assign' turns
up few matches; the seem to be normal use-case. Test fbvector assign
with self-iterators in order (i.e. fbv.assign(fbv.begin(), fbv.end()));
this seems to work fine.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D535012
---
 folly/FBVector.h            | 12 ------------
 folly/test/FBVectorTest.cpp | 22 ++++++++++++++++++++++
 2 files changed, 22 insertions(+), 12 deletions(-)

diff --git a/folly/FBVector.h b/folly/FBVector.h
index e09eeda3..d275ec17 100644
--- a/folly/FBVector.h
+++ b/folly/FBVector.h
@@ -376,13 +376,6 @@ private:
   void assignImpl(InputIterator first, InputIterator last, boost::false_type) {
     // Pair of iterators
     if (fbvector_detail::isForwardIterator<InputIterator>::value) {
-      if (b_ <= &*first && &*first < e_) {
-        // Aliased assign, work on the side
-        fbvector result(first, last);
-        result.swap(*this);
-        return;
-      }
-
       auto const oldSize = size();
       auto const newSize = std::distance(first, last);
 
@@ -802,10 +795,6 @@ private:
       // Can compute distance
       auto const n = std::distance(first, last);
       if (e_ + n >= z_) {
-        if (b_ <= &*first && &*first < e_) {
-          // Ew, aliased insert
-          goto conservative;
-        }
         auto const m = position - b_;
         reserve(size() + n);
         position = b_ + m;
@@ -828,7 +817,6 @@ private:
     } else {
       // Cannot compute distance, crappy approach
       // TODO: OPTIMIZE
-      conservative:
       fbvector result(cbegin(), position);
       auto const offset = result.size();
       FOR_EACH_RANGE (i, first, last) {
diff --git a/folly/test/FBVectorTest.cpp b/folly/test/FBVectorTest.cpp
index 9427dc27..98212e18 100644
--- a/folly/test/FBVectorTest.cpp
+++ b/folly/test/FBVectorTest.cpp
@@ -223,6 +223,28 @@ TEST(FBVector, task858056) {
   EXPECT_EQ("Cycle detected: [baz] [bar] [foo] ", message);
 }
 
+TEST(FBVector, move_iterator) {
+  fbvector<int> base = { 0, 1, 2 };
+
+  auto cp1 = base;
+  fbvector<int> fbvi1(std::make_move_iterator(cp1.begin()),
+                      std::make_move_iterator(cp1.end()));
+  EXPECT_EQ(fbvi1, base);
+
+  auto cp2 = base;
+  fbvector<int> fbvi2;
+  fbvi2.assign(std::make_move_iterator(cp2.begin()),
+               std::make_move_iterator(cp2.end()));
+  EXPECT_EQ(fbvi2, base);
+
+  auto cp3 = base;
+  fbvector<int> fbvi3;
+  fbvi3.insert(fbvi3.end(),
+               std::make_move_iterator(cp3.begin()),
+               std::make_move_iterator(cp3.end()));
+  EXPECT_EQ(fbvi3, base);
+}
+
 int main(int argc, char** argv) {
   testing::InitGoogleTest(&argc, argv);
   google::ParseCommandLineFlags(&argc, &argv, true);
-- 
2.34.1