Refactor handling of input records.
Introduce HInstruction::GetInputRecords(), a new virtual
function that returns an ArrayRef<> to all input records.
Implement all other functions dealing with input records as
wrappers around GetInputRecords(). Rewrite functions that
previously used multiple virtual calls to deal with input
records, especially in loops, to prefetch the ArrayRef<>
only once for each instruction. Besides avoiding all the
extra calls, this also allows the compiler (clang++) to
perform additional optimizations.
This speeds up the Nexus 5 boot image compilation by ~0.5s
(4% of "Compile Dex File", 2% of dex2oat time) on AOSP ToT.
Change-Id: Id8ebe0fb9405e38d918972a11bd724146e4ca578
diff --git a/compiler/utils/transform_iterator_test.cc b/compiler/utils/transform_iterator_test.cc
new file mode 100644
index 0000000..dbb4779
--- /dev/null
+++ b/compiler/utils/transform_iterator_test.cc
@@ -0,0 +1,533 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <algorithm>
+#include <forward_list>
+#include <list>
+#include <type_traits>
+#include <vector>
+
+#include <array>
+
+#include "gtest/gtest.h"
+
+#include "utils/transform_iterator.h"
+
+namespace art {
+
+namespace { // anonymous namespace
+
+struct ValueHolder {
+ // Deliberately not explicit.
+ ValueHolder(int v) : value(v) { } // NOLINT
+ int value;
+};
+
+bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) {
+ return lhs.value == rhs.value;
+}
+
+} // anonymous namespace
+
+TEST(TransformIterator, VectorAdd1) {
+ auto add1 = [](const ValueHolder& h) { return h.value + 1; }; // NOLINT [readability/braces]
+ std::vector<ValueHolder> input({ 1, 7, 3, 8 });
+ std::vector<int> output;
+
+ using vector_titer = decltype(MakeTransformIterator(input.begin(), add1));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_titer::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+ static_assert(std::is_same<vector_titer, vector_titer::pointer>::value, "pointer");
+ static_assert(std::is_same<int, vector_titer::reference>::value, "reference");
+
+ using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), add1));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_ctiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
+ static_assert(std::is_same<vector_ctiter, vector_ctiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, vector_ctiter::reference>::value, "reference");
+
+ using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), add1));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_rtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<vector_rtiter, vector_rtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, vector_rtiter::reference>::value, "reference");
+
+ using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), add1));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_crtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<vector_crtiter, vector_crtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, vector_crtiter::reference>::value, "reference");
+
+ std::copy(MakeTransformIterator(input.begin(), add1),
+ MakeTransformIterator(input.end(), add1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.cbegin(), add1),
+ MakeTransformIterator(input.cend(), add1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.rbegin(), add1),
+ MakeTransformIterator(input.rend(), add1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.crbegin(), add1),
+ MakeTransformIterator(input.crend(), add1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output);
+ output.clear();
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.begin(), add1)[i]);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cbegin(), add1)[i]);
+ ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rbegin(), add1)[index_from_rbegin]);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crbegin(), add1)[index_from_rbegin]);
+ ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.end(), add1)[index_from_end]);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cend(), add1)[index_from_end]);
+ ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rend(), add1)[index_from_rend]);
+ ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crend(), add1)[index_from_rend]);
+
+ ASSERT_EQ(MakeTransformIterator(input.begin(), add1) + i,
+ MakeTransformIterator(input.begin() + i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.cbegin(), add1) + i,
+ MakeTransformIterator(input.cbegin() + i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.rbegin(), add1) + i,
+ MakeTransformIterator(input.rbegin() + i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.crbegin(), add1) + i,
+ MakeTransformIterator(input.crbegin() + i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.end(), add1) - i,
+ MakeTransformIterator(input.end() - i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.cend(), add1) - i,
+ MakeTransformIterator(input.cend() - i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.rend(), add1) - i,
+ MakeTransformIterator(input.rend() - i, add1));
+ ASSERT_EQ(MakeTransformIterator(input.crend(), add1) - i,
+ MakeTransformIterator(input.crend() - i, add1));
+ }
+ ASSERT_EQ(input.end(),
+ (MakeTransformIterator(input.begin(), add1) + input.size()).base());
+ ASSERT_EQ(MakeTransformIterator(input.end(), add1) - MakeTransformIterator(input.begin(), add1),
+ static_cast<ptrdiff_t>(input.size()));
+
+ // Test iterator->const_iterator conversion and comparison.
+ auto it = MakeTransformIterator(input.begin(), add1);
+ decltype(MakeTransformIterator(input.cbegin(), add1)) cit = it;
+ static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+ ASSERT_EQ(it, cit);
+ auto rit = MakeTransformIterator(input.rbegin(), add1);
+ decltype(MakeTransformIterator(input.crbegin(), add1)) crit(rit);
+ static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different");
+ ASSERT_EQ(rit, crit);
+}
+
+TEST(TransformIterator, ListSub1) {
+ auto sub1 = [](const ValueHolder& h) { return h.value - 1; }; // NOLINT [readability/braces]
+ std::list<ValueHolder> input({ 2, 3, 5, 7, 11 });
+ std::vector<int> output;
+
+ using list_titer = decltype(MakeTransformIterator(input.begin(), sub1));
+ static_assert(std::is_same<std::bidirectional_iterator_tag,
+ list_titer::iterator_category>::value, "category");
+ static_assert(std::is_same<int, list_titer::value_type>::value, "value_type");
+ static_assert(std::is_same<list_titer, list_titer::pointer>::value, "pointer");
+ static_assert(std::is_same<int, list_titer::reference>::value, "reference");
+
+ using list_ctiter = decltype(MakeTransformIterator(input.cbegin(), sub1));
+ static_assert(std::is_same<std::bidirectional_iterator_tag,
+ list_ctiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, list_ctiter::value_type>::value, "value_type");
+ static_assert(std::is_same<list_ctiter, list_ctiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, list_ctiter::reference>::value, "reference");
+
+ using list_rtiter = decltype(MakeTransformIterator(input.rbegin(), sub1));
+ static_assert(std::is_same<std::bidirectional_iterator_tag,
+ list_rtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, list_rtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<list_rtiter, list_rtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, list_rtiter::reference>::value, "reference");
+
+ using list_crtiter = decltype(MakeTransformIterator(input.crbegin(), sub1));
+ static_assert(std::is_same<std::bidirectional_iterator_tag,
+ list_crtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, list_crtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<list_crtiter, list_crtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, list_crtiter::reference>::value, "reference");
+
+ std::copy(MakeTransformIterator(input.begin(), sub1),
+ MakeTransformIterator(input.end(), sub1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.cbegin(), sub1),
+ MakeTransformIterator(input.cend(), sub1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.rbegin(), sub1),
+ MakeTransformIterator(input.rend(), sub1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.crbegin(), sub1),
+ MakeTransformIterator(input.crend(), sub1),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1 }), output);
+ output.clear();
+
+ // Test iterator->const_iterator conversion and comparison.
+ auto it = MakeTransformIterator(input.begin(), sub1);
+ decltype(MakeTransformIterator(input.cbegin(), sub1)) cit = it;
+ static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+ ASSERT_EQ(it, cit);
+}
+
+TEST(TransformIterator, ForwardListSub1) {
+ auto mul3 = [](const ValueHolder& h) { return h.value * 3; }; // NOLINT [readability/braces]
+ std::forward_list<ValueHolder> input({ 1, 1, 2, 3, 5, 8 });
+ std::vector<int> output;
+
+ using flist_titer = decltype(MakeTransformIterator(input.begin(), mul3));
+ static_assert(std::is_same<std::forward_iterator_tag,
+ flist_titer::iterator_category>::value, "category");
+ static_assert(std::is_same<int, flist_titer::value_type>::value, "value_type");
+ static_assert(std::is_same<flist_titer, flist_titer::pointer>::value, "pointer");
+ static_assert(std::is_same<int, flist_titer::reference>::value, "reference");
+
+ using flist_ctiter = decltype(MakeTransformIterator(input.cbegin(), mul3));
+ static_assert(std::is_same<std::forward_iterator_tag,
+ flist_ctiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, flist_ctiter::value_type>::value, "value_type");
+ static_assert(std::is_same<flist_ctiter, flist_ctiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int, flist_ctiter::reference>::value, "reference");
+
+ std::copy(MakeTransformIterator(input.begin(), mul3),
+ MakeTransformIterator(input.end(), mul3),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.cbegin(), mul3),
+ MakeTransformIterator(input.cend(), mul3),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output);
+ output.clear();
+
+ // Test iterator->const_iterator conversion and comparison.
+ auto it = MakeTransformIterator(input.begin(), mul3);
+ decltype(MakeTransformIterator(input.cbegin(), mul3)) cit = it;
+ static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+ ASSERT_EQ(it, cit);
+}
+
+TEST(TransformIterator, VectorConstReference) {
+ auto ref = [](const ValueHolder& h) -> const int& { return h.value; }; // NOLINT [readability/braces]
+ std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
+ std::vector<int> output;
+
+ using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_titer::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+ static_assert(std::is_same<const int*, vector_titer::pointer>::value, "pointer");
+ static_assert(std::is_same<const int&, vector_titer::reference>::value, "reference");
+
+ using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_ctiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
+ static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer");
+ static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference");
+
+ using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_rtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<const int*, vector_rtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<const int&, vector_rtiter::reference>::value, "reference");
+
+ using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_crtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference");
+
+ std::copy(MakeTransformIterator(input.begin(), ref),
+ MakeTransformIterator(input.end(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.cbegin(), ref),
+ MakeTransformIterator(input.cend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.rbegin(), ref),
+ MakeTransformIterator(input.rend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.crbegin(), ref),
+ MakeTransformIterator(input.crend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+ output.clear();
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]);
+ ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]);
+ ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]);
+ ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]);
+
+ ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
+ MakeTransformIterator(input.begin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i,
+ MakeTransformIterator(input.cbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
+ MakeTransformIterator(input.rbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i,
+ MakeTransformIterator(input.crbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
+ MakeTransformIterator(input.end() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i,
+ MakeTransformIterator(input.cend() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
+ MakeTransformIterator(input.rend() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i,
+ MakeTransformIterator(input.crend() - i, ref));
+ }
+ ASSERT_EQ(input.end(),
+ (MakeTransformIterator(input.begin(), ref) + input.size()).base());
+ ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
+ static_cast<ptrdiff_t>(input.size()));
+}
+
+TEST(TransformIterator, VectorNonConstReference) {
+ auto ref = [](ValueHolder& h) -> int& { return h.value; }; // NOLINT [readability/braces]
+ std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
+ std::vector<int> output;
+
+ using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_titer::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+ static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer");
+ static_assert(std::is_same<int&, vector_titer::reference>::value, "reference");
+
+ using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_rtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference");
+
+ std::copy(MakeTransformIterator(input.begin(), ref),
+ MakeTransformIterator(input.end(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.rbegin(), ref),
+ MakeTransformIterator(input.rend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+ output.clear();
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
+ ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
+ ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
+ ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
+
+ ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
+ MakeTransformIterator(input.begin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
+ MakeTransformIterator(input.rbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
+ MakeTransformIterator(input.end() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
+ MakeTransformIterator(input.rend() - i, ref));
+ }
+ ASSERT_EQ(input.end(),
+ (MakeTransformIterator(input.begin(), ref) + input.size()).base());
+ ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
+ static_cast<ptrdiff_t>(input.size()));
+
+ // Test writing through the transform iterator.
+ std::list<int> transform_input({ 1, -1, 2, -2, 3, -3 });
+ std::vector<ValueHolder> transformed(transform_input.size(), 0);
+ std::transform(transform_input.begin(),
+ transform_input.end(),
+ MakeTransformIterator(transformed.begin(), ref),
+ [](int v) { return -2 * v; });
+ ASSERT_EQ(std::vector<ValueHolder>({ -2, 2, -4, 4, -6, 6 }), transformed);
+}
+
+TEST(TransformIterator, VectorConstAndNonConstReference) {
+ struct Ref {
+ int& operator()(ValueHolder& h) const { return h.value; }
+ const int& operator()(const ValueHolder& h) const { return h.value; }
+ };
+ Ref ref;
+ std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
+ std::vector<int> output;
+
+ using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_titer::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
+ static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer");
+ static_assert(std::is_same<int&, vector_titer::reference>::value, "reference");
+
+ using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_ctiter::iterator_category>::value, "category");
+ // static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
+ static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer");
+ static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference");
+
+ using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_rtiter::iterator_category>::value, "category");
+ static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference");
+
+ using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref));
+ static_assert(std::is_same<std::random_access_iterator_tag,
+ vector_crtiter::iterator_category>::value, "category");
+ // static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
+ static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer");
+ static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference");
+
+ std::copy(MakeTransformIterator(input.begin(), ref),
+ MakeTransformIterator(input.end(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.cbegin(), ref),
+ MakeTransformIterator(input.cend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.rbegin(), ref),
+ MakeTransformIterator(input.rend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+ output.clear();
+
+ std::copy(MakeTransformIterator(input.crbegin(), ref),
+ MakeTransformIterator(input.crend(), ref),
+ std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
+ output.clear();
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]);
+ ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]);
+ ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]);
+ ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
+ ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]);
+
+ ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
+ MakeTransformIterator(input.begin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i,
+ MakeTransformIterator(input.cbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
+ MakeTransformIterator(input.rbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i,
+ MakeTransformIterator(input.crbegin() + i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
+ MakeTransformIterator(input.end() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i,
+ MakeTransformIterator(input.cend() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
+ MakeTransformIterator(input.rend() - i, ref));
+ ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i,
+ MakeTransformIterator(input.crend() - i, ref));
+ }
+ ASSERT_EQ(input.end(),
+ (MakeTransformIterator(input.begin(), ref) + input.size()).base());
+ ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
+ static_cast<ptrdiff_t>(input.size()));
+
+ // Test iterator->const_iterator conversion and comparison.
+ auto it = MakeTransformIterator(input.begin(), ref);
+ decltype(MakeTransformIterator(input.cbegin(), ref)) cit = it;
+ static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
+ ASSERT_EQ(it, cit);
+ auto rit = MakeTransformIterator(input.rbegin(), ref);
+ decltype(MakeTransformIterator(input.crbegin(), ref)) crit(rit);
+ static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different");
+ ASSERT_EQ(rit, crit);
+
+ // Test writing through the transform iterator.
+ std::list<int> transform_input({ 42, 73, 11, 17 });
+ std::vector<ValueHolder> transformed(transform_input.size(), 0);
+ std::transform(transform_input.begin(),
+ transform_input.end(),
+ MakeTransformIterator(transformed.begin(), ref),
+ [](int v) { return -v; });
+ ASSERT_EQ(std::vector<ValueHolder>({ -42, -73, -11, -17 }), transformed);
+}
+
+TEST(TransformIterator, TransformRange) {
+ auto ref = [](ValueHolder& h) -> int& { return h.value; }; // NOLINT [readability/braces]
+ std::vector<ValueHolder> data({ 1, 0, 1, 3, 1, 0 });
+
+ for (int& v : MakeTransformRange(data, ref)) {
+ v += 11;
+ }
+ ASSERT_EQ(std::vector<ValueHolder>({ 12, 11, 12, 14, 12, 11 }), data);
+}
+
+} // namespace art