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/array_ref.h b/compiler/utils/array_ref.h
index 5c33639..8dc9ab4 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -39,9 +39,6 @@
*/
template <typename T>
class ArrayRef {
- private:
- struct tag { };
-
public:
typedef T value_type;
typedef T& reference;
@@ -63,14 +60,14 @@
template <size_t size>
explicit constexpr ArrayRef(T (&array)[size])
- : array_(array), size_(size) {
+ : array_(array), size_(size) {
}
- template <typename U, size_t size>
- explicit constexpr ArrayRef(U (&array)[size],
- typename std::enable_if<std::is_same<T, const U>::value, tag>::type
- t ATTRIBUTE_UNUSED = tag())
- : array_(array), size_(size) {
+ template <typename U,
+ size_t size,
+ typename = typename std::enable_if<std::is_same<T, const U>::value>::type>
+ explicit constexpr ArrayRef(U (&array)[size])
+ : array_(array), size_(size) {
}
constexpr ArrayRef(T* array_in, size_t size_in)
@@ -165,13 +162,21 @@
value_type* data() { return array_; }
const value_type* data() const { return array_; }
- ArrayRef SubArray(size_type pos) const {
- return SubArray(pos, size_ - pos);
+ ArrayRef SubArray(size_type pos) {
+ return SubArray(pos, size() - pos);
}
- ArrayRef SubArray(size_type pos, size_type length) const {
+ ArrayRef<const T> SubArray(size_type pos) const {
+ return SubArray(pos, size() - pos);
+ }
+ ArrayRef SubArray(size_type pos, size_type length) {
DCHECK_LE(pos, size());
DCHECK_LE(length, size() - pos);
- return ArrayRef(array_ + pos, length);
+ return ArrayRef(data() + pos, length);
+ }
+ ArrayRef<const T> SubArray(size_type pos, size_type length) const {
+ DCHECK_LE(pos, size());
+ DCHECK_LE(length, size() - pos);
+ return ArrayRef<const T>(data() + pos, length);
}
private:
diff --git a/compiler/utils/transform_array_ref.h b/compiler/utils/transform_array_ref.h
new file mode 100644
index 0000000..6297b88
--- /dev/null
+++ b/compiler/utils/transform_array_ref.h
@@ -0,0 +1,188 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_
+#define ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_
+
+#include <type_traits>
+
+#include "utils/array_ref.h"
+#include "utils/transform_iterator.h"
+
+namespace art {
+
+/**
+ * @brief An ArrayRef<> wrapper that uses a transformation function for element access.
+ */
+template <typename BaseType, typename Function>
+class TransformArrayRef {
+ private:
+ using Iter = TransformIterator<typename ArrayRef<BaseType>::iterator, Function>;
+
+ // The Function may take a non-const reference, so const_iterator may not exist.
+ using FallbackConstIter = std::iterator<std::random_access_iterator_tag, void, void, void, void>;
+ using PreferredConstIter =
+ TransformIterator<typename ArrayRef<BaseType>::const_iterator, Function>;
+ template <typename F, typename = typename std::result_of<F(const BaseType&)>::type>
+ static PreferredConstIter ConstIterHelper(int&);
+ template <typename F>
+ static FallbackConstIter ConstIterHelper(const int&);
+
+ using ConstIter = decltype(ConstIterHelper<Function>(*reinterpret_cast<int*>(0)));
+
+ public:
+ using value_type = typename Iter::value_type;
+ using reference = typename Iter::reference;
+ using const_reference = typename ConstIter::reference;
+ using pointer = typename Iter::pointer;
+ using const_pointer = typename ConstIter::pointer;
+ using iterator = Iter;
+ using const_iterator = typename std::conditional<
+ std::is_same<ConstIter, FallbackConstIter>::value,
+ void,
+ ConstIter>::type;
+ using reverse_iterator = std::reverse_iterator<Iter>;
+ using const_reverse_iterator = typename std::conditional<
+ std::is_same<ConstIter, FallbackConstIter>::value,
+ void,
+ std::reverse_iterator<ConstIter>>::type;
+ using difference_type = typename ArrayRef<BaseType>::difference_type;
+ using size_type = typename ArrayRef<BaseType>::size_type;
+
+ // Constructors.
+
+ TransformArrayRef(const TransformArrayRef& other) = default;
+
+ template <typename OtherBT>
+ TransformArrayRef(const ArrayRef<OtherBT>& base, Function fn)
+ : data_(base, fn) { }
+
+ // Assignment operators.
+
+ TransformArrayRef& operator=(const TransformArrayRef& other) = default;
+
+ template <typename OtherBT,
+ typename = typename std::enable_if<std::is_same<BaseType, const OtherBT>::value>::type>
+ TransformArrayRef& operator=(const TransformArrayRef<OtherBT, Function>& other) {
+ return *this = TransformArrayRef(other.base(), other.GetFunction());
+ }
+
+ // Destructor.
+ ~TransformArrayRef() = default;
+
+ // Iterators.
+ iterator begin() { return MakeIterator(base().begin()); }
+ const_iterator begin() const { return MakeIterator(base().cbegin()); }
+ const_iterator cbegin() const { return MakeIterator(base().cbegin()); }
+ iterator end() { return MakeIterator(base().end()); }
+ const_iterator end() const { MakeIterator(base().cend()); }
+ const_iterator cend() const { return MakeIterator(base().cend()); }
+ reverse_iterator rbegin() { return reverse_iterator(end()); }
+ const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
+ const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); }
+ reverse_iterator rend() { return reverse_iterator(begin()); }
+ const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
+ const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); }
+
+ // Size.
+ size_type size() const { return base().size(); }
+ bool empty() const { return base().empty(); }
+
+ // Element access. NOTE: Not providing data().
+
+ reference operator[](size_type n) { return GetFunction()(base()[n]); }
+ const_reference operator[](size_type n) const { return GetFunction()(base()[n]); }
+
+ reference front() { return GetFunction()(base().front()); }
+ const_reference front() const { return GetFunction()(base().front()); }
+
+ reference back() { return GetFunction()(base().back()); }
+ const_reference back() const { return GetFunction()(base().back()); }
+
+ TransformArrayRef SubArray(size_type pos) {
+ return TransformArrayRef(base().subarray(pos), GetFunction());
+ }
+ TransformArrayRef SubArray(size_type pos) const {
+ return TransformArrayRef(base().subarray(pos), GetFunction());
+ }
+ TransformArrayRef SubArray(size_type pos, size_type length) const {
+ return TransformArrayRef(base().subarray(pos, length), GetFunction());
+ }
+
+ // Retrieve the base ArrayRef<>.
+ ArrayRef<BaseType> base() {
+ return data_.base_;
+ }
+ ArrayRef<const BaseType> base() const {
+ return ArrayRef<const BaseType>(data_.base_);
+ }
+
+ private:
+ // Allow EBO for state-less Function.
+ struct Data : Function {
+ public:
+ Data(ArrayRef<BaseType> base, Function fn) : Function(fn), base_(base) { }
+
+ ArrayRef<BaseType> base_;
+ };
+
+ const Function& GetFunction() const {
+ return static_cast<const Function&>(data_);
+ }
+
+ template <typename BaseIterator>
+ auto MakeIterator(BaseIterator base) const {
+ return MakeTransformIterator(base, GetFunction());
+ }
+
+ Data data_;
+};
+
+template <typename BaseType, typename Function>
+bool operator==(const TransformArrayRef<BaseType, Function>& lhs,
+ const TransformArrayRef<BaseType, Function>& rhs) {
+ return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+}
+
+template <typename BaseType, typename Function>
+bool operator!=(const TransformArrayRef<BaseType, Function>& lhs,
+ const TransformArrayRef<BaseType, Function>& rhs) {
+ return !(lhs == rhs);
+}
+
+template <typename ValueType, typename Function>
+TransformArrayRef<ValueType, Function> MakeTransformArrayRef(
+ ArrayRef<ValueType> container, Function f) {
+ return TransformArrayRef<ValueType, Function>(container, f);
+}
+
+template <typename Container, typename Function>
+TransformArrayRef<typename Container::value_type, Function> MakeTransformArrayRef(
+ Container& container, Function f) {
+ return TransformArrayRef<typename Container::value_type, Function>(
+ ArrayRef<typename Container::value_type>(container.data(), container.size()), f);
+}
+
+template <typename Container, typename Function>
+TransformArrayRef<const typename Container::value_type, Function> MakeTransformArrayRef(
+ const Container& container, Function f) {
+ return TransformArrayRef<const typename Container::value_type, Function>(
+ ArrayRef<const typename Container::value_type>(container.data(), container.size()), f);
+}
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_
diff --git a/compiler/utils/transform_array_ref_test.cc b/compiler/utils/transform_array_ref_test.cc
new file mode 100644
index 0000000..2593fad
--- /dev/null
+++ b/compiler/utils/transform_array_ref_test.cc
@@ -0,0 +1,165 @@
+/*
+ * 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 <vector>
+
+#include "gtest/gtest.h"
+
+#include "utils/transform_array_ref.h"
+
+namespace art {
+
+namespace { // anonymous namespace
+
+struct ValueHolder {
+ // Deliberately not explicit.
+ ValueHolder(int v) : value(v) { } // NOLINT
+ int value;
+};
+
+ATTRIBUTE_UNUSED bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) {
+ return lhs.value == rhs.value;
+}
+
+} // anonymous namespace
+
+TEST(TransformArrayRef, ConstRefAdd1) {
+ auto add1 = [](const ValueHolder& h) { return h.value + 1; }; // NOLINT [readability/braces]
+ std::vector<ValueHolder> input({ 7, 6, 4, 0 });
+ std::vector<int> output;
+
+ auto taref = MakeTransformArrayRef(input, add1);
+ using TarefIter = decltype(taref)::iterator;
+ using ConstTarefIter = decltype(taref)::const_iterator;
+ static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type");
+ static_assert(std::is_same<TarefIter, decltype(taref)::pointer>::value, "pointer");
+ static_assert(std::is_same<int, decltype(taref)::reference>::value, "reference");
+ static_assert(std::is_same<ConstTarefIter, decltype(taref)::const_pointer>::value,
+ "const_pointer");
+ static_assert(std::is_same<int, decltype(taref)::const_reference>::value, "const_reference");
+
+ std::copy(taref.begin(), taref.end(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 7, 5, 1 }), output);
+ output.clear();
+
+ std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 8, 7, 5, 1 }), output);
+ output.clear();
+
+ std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 5, 7, 8 }), output);
+ output.clear();
+
+ std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 5, 7, 8 }), output);
+ output.clear();
+
+ ASSERT_EQ(input.size(), taref.size());
+ ASSERT_EQ(input.empty(), taref.empty());
+ ASSERT_EQ(input.front().value + 1, taref.front());
+ ASSERT_EQ(input.back().value + 1, taref.back());
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value + 1, taref[i]);
+ }
+}
+
+TEST(TransformArrayRef, NonConstRefSub1) {
+ auto sub1 = [](ValueHolder& h) { return h.value - 1; }; // NOLINT [readability/braces]
+ std::vector<ValueHolder> input({ 4, 4, 5, 7, 10 });
+ std::vector<int> output;
+
+ auto taref = MakeTransformArrayRef(input, sub1);
+ using TarefIter = decltype(taref)::iterator;
+ static_assert(std::is_same<void, decltype(taref)::const_iterator>::value, "const_iterator");
+ static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type");
+ static_assert(std::is_same<TarefIter, decltype(taref)::pointer>::value, "pointer");
+ static_assert(std::is_same<int, decltype(taref)::reference>::value, "reference");
+ static_assert(std::is_same<void, decltype(taref)::const_pointer>::value, "const_pointer");
+ static_assert(std::is_same<void, decltype(taref)::const_reference>::value, "const_reference");
+
+ std::copy(taref.begin(), taref.end(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 3, 3, 4, 6, 9 }), output);
+ output.clear();
+
+ std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 9, 6, 4, 3, 3 }), output);
+ output.clear();
+
+ ASSERT_EQ(input.size(), taref.size());
+ ASSERT_EQ(input.empty(), taref.empty());
+ ASSERT_EQ(input.front().value - 1, taref.front());
+ ASSERT_EQ(input.back().value - 1, taref.back());
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value - 1, taref[i]);
+ }
+}
+
+TEST(TransformArrayRef, ConstAndNonConstRef) {
+ 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({ 1, 0, 1, 0, 3, 1 });
+ std::vector<int> output;
+
+ auto taref = MakeTransformArrayRef(input, ref);
+ static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type");
+ static_assert(std::is_same<int*, decltype(taref)::pointer>::value, "pointer");
+ static_assert(std::is_same<int&, decltype(taref)::reference>::value, "reference");
+ static_assert(std::is_same<const int*, decltype(taref)::const_pointer>::value, "const_pointer");
+ static_assert(std::is_same<const int&, decltype(taref)::const_reference>::value,
+ "const_reference");
+
+ std::copy(taref.begin(), taref.end(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output);
+ output.clear();
+
+ std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output);
+ output.clear();
+
+ std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output);
+ output.clear();
+
+ std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output));
+ ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output);
+ output.clear();
+
+ ASSERT_EQ(input.size(), taref.size());
+ ASSERT_EQ(input.empty(), taref.empty());
+ ASSERT_EQ(input.front().value, taref.front());
+ ASSERT_EQ(input.back().value, taref.back());
+
+ for (size_t i = 0; i != input.size(); ++i) {
+ ASSERT_EQ(input[i].value, taref[i]);
+ }
+
+ // Test writing through the transform iterator.
+ std::vector<int> transform_input({ 24, 37, 11, 71 });
+ std::vector<ValueHolder> transformed(transform_input.size(), 0);
+ taref = MakeTransformArrayRef(transformed, ref);
+ for (size_t i = 0; i != transform_input.size(); ++i) {
+ taref[i] = transform_input[i];
+ }
+ ASSERT_EQ(std::vector<ValueHolder>({ 24, 37, 11, 71 }), transformed);
+}
+
+} // namespace art
diff --git a/compiler/utils/transform_iterator.h b/compiler/utils/transform_iterator.h
new file mode 100644
index 0000000..f0769d4
--- /dev/null
+++ b/compiler/utils/transform_iterator.h
@@ -0,0 +1,182 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
+#define ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
+
+#include <iterator>
+#include <type_traits>
+
+#include "base/iteration_range.h"
+
+namespace art {
+
+// The transform iterator transforms values from the base iterator with a given
+// transformation function. It can serve as a replacement for std::transform(), i.e.
+// std::copy(MakeTransformIterator(begin, f), MakeTransformIterator(end, f), out)
+// is equivalent to
+// std::transform(begin, end, f)
+// If the function returns an l-value reference or a wrapper that supports assignment,
+// the TransformIterator can be used also as an output iterator, i.e.
+// std::copy(begin, end, MakeTransformIterator(out, f))
+// is equivalent to
+// for (auto it = begin; it != end; ++it) {
+// f(*out++) = *it;
+// }
+template <typename BaseIterator, typename Function>
+class TransformIterator {
+ private:
+ static_assert(std::is_base_of<
+ std::input_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "Transform iterator base must be an input iterator.");
+
+ using InputType =
+ typename std::conditional<
+ std::is_same<void, typename std::iterator_traits<BaseIterator>::reference>::value,
+ typename std::iterator_traits<BaseIterator>::value_type,
+ typename std::iterator_traits<BaseIterator>::reference>::type;
+ using ResultType = typename std::result_of<Function(InputType)>::type;
+
+ public:
+ using iterator_category = typename std::iterator_traits<BaseIterator>::iterator_category;
+ using value_type =
+ typename std::remove_const<typename std::remove_reference<ResultType>::type>::type;
+ using difference_type = typename std::iterator_traits<BaseIterator>::difference_type;
+ using pointer = typename std::conditional<
+ std::is_reference<ResultType>::value,
+ typename std::add_pointer<typename std::remove_reference<ResultType>::type>::type,
+ TransformIterator>::type;
+ using reference = ResultType;
+
+ TransformIterator(BaseIterator base, Function fn)
+ : data_(base, fn) { }
+
+ template <typename OtherBI>
+ TransformIterator(const TransformIterator<OtherBI, Function>& other)
+ : data_(other.base(), other.GetFunction()) {
+ }
+
+ TransformIterator& operator++() {
+ ++data_.base_;
+ return *this;
+ }
+
+ TransformIterator& operator++(int) {
+ TransformIterator tmp(*this);
+ ++*this;
+ return tmp;
+ }
+
+ TransformIterator& operator--() {
+ static_assert(
+ std::is_base_of<std::bidirectional_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be bidirectional iterator to use operator--()");
+ --data_.base_;
+ return *this;
+ }
+
+ TransformIterator& operator--(int) {
+ TransformIterator tmp(*this);
+ --*this;
+ return tmp;
+ }
+
+ reference operator*() const {
+ return GetFunction()(*base());
+ }
+
+ reference operator[](difference_type n) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator[]");
+ return GetFunction()(base()[n]);
+ }
+
+ TransformIterator operator+(difference_type n) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator+");
+ return TransformIterator(base() + n, GetFunction());
+ }
+
+ TransformIterator operator-(difference_type n) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator-");
+ return TransformIterator(base() - n, GetFunction());
+ }
+
+ difference_type operator-(const TransformIterator& other) const {
+ static_assert(
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<BaseIterator>::iterator_category>::value,
+ "BaseIterator must be random access iterator to use operator-");
+ return base() - other.base();
+ }
+
+ // Retrieve the base iterator.
+ BaseIterator base() const {
+ return data_.base_;
+ }
+
+ // Retrieve the transformation function.
+ const Function& GetFunction() const {
+ return static_cast<const Function&>(data_);
+ }
+
+ private:
+ // Allow EBO for state-less Function.
+ struct Data : Function {
+ public:
+ Data(BaseIterator base, Function fn) : Function(fn), base_(base) { }
+
+ BaseIterator base_;
+ };
+
+ Data data_;
+};
+
+template <typename BaseIterator1, typename BaseIterator2, typename Function>
+bool operator==(const TransformIterator<BaseIterator1, Function>& lhs,
+ const TransformIterator<BaseIterator2, Function>& rhs) {
+ return lhs.base() == rhs.base();
+}
+
+template <typename BaseIterator1, typename BaseIterator2, typename Function>
+bool operator!=(const TransformIterator<BaseIterator1, Function>& lhs,
+ const TransformIterator<BaseIterator2, Function>& rhs) {
+ return !(lhs == rhs);
+}
+
+template <typename BaseIterator, typename Function>
+TransformIterator<BaseIterator, Function> MakeTransformIterator(BaseIterator base, Function f) {
+ return TransformIterator<BaseIterator, Function>(base, f);
+}
+
+template <typename BaseRange, typename Function>
+auto MakeTransformRange(BaseRange& range, Function f) {
+ return MakeIterationRange(MakeTransformIterator(range.begin(), f),
+ MakeTransformIterator(range.end(), f));
+}
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_
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