[ADT] [WIP] Add MutableRange class

[abrachet]

Summary

MutableRange provides an interface to effectively make a const container mutable without copying every element or modifying the const container in any way.

This will eventually be used in D64281.

[jhenderson]

Nice work so far. I think it would be more natural to me if the "main" template argument was that of the underlying container, rather than the iterator. This shouldn't affect the functionality, if I've followed it correctly.

I've got a number of other comments, but don't want to overload things too much in the first instance.

llvm/include/llvm/Support/UpdatableRange.h

1 ↗

(On Diff #208856)

Don't forget to include LLVM copyright headers, even in WIP code.

35 ↗

(On Diff #208856)

Is the KeyType type useful in this version?

49 ↗

(On Diff #208856)

In the current version, you don't need this, since you don't have any way of removing anything.

65 ↗

(On Diff #208856)

Isn't this simply not generated if another constructor was defined?

71 ↗

(On Diff #208856)

Use size_t.

72 ↗

(On Diff #208856)

Rather than this, have you considered using std::transform?

75 ↗

(On Diff #208856)

Make sure to include comments for each public member function describing what it does.

95 ↗

(On Diff #208856)

You'll probably want to make this return an Expected or similar, I suspect, rather than assert.

[abrachet]

Moved files from Support to ADT. Removed base class because it wasn't adding anything. Changed enable_if to specialize on the container type, between AssociativeContainer and SequenceContainer's. Added doxygen comments for all public methods. Added collect() method to return the UpdatableRange as the same type of the original container. Updated unit test to be more comprehensive and use test fixtures. Addressed review comments.

[abrachet]

llvm/include/llvm/ADT/UpdatableRange.h

122 ↗

(On Diff #209123)

Should this return Error?

[jhenderson]

If you haven't already, it's worth looking at the other ADT classes like SmallVector to make sure your code matches the same style etc used there.

I think the name "MutableRange" might be more consistent with naming schemes within LLVM.

Overall, I quite like this. I think it's at the point where it's worth getting a wider audience by adding some more people as reviewers.

llvm/include/llvm/ADT/UpdatableRange.h

1 ↗

(On Diff #209123)

Minor point this but I believe this needs to mention c++ somewhere so that editors can detect the language properly. I'm also not sure the rest of the text makes much sense... ;)

55 ↗

(On Diff #209123)

Nit: replacment -> replacement

87–88 ↗

(On Diff #209123)

Nit: clang-format?

122 ↗

(On Diff #209123)

Actually, looking at SmallVector, it looks like I was wrong to encourage you to use Expected below (it uses asserts too), so this should remain an assert.

[abrachet]

Addressed review comments. Renamed to MutableRange

[abrachet]

llvm/include/llvm/ADT/UpdatableRange.h

1 ↗

(On Diff #209123)

I got caught copy and pasting on that one! :)

[abrachet]

clang-format

[jhenderson]

llvm/include/llvm/ADT/MutableRange.h

53

Why is the alignas needed?

68–69

Begin and End? Probably even UnderlyingBegin and UnderlyingEnd to disambiguate

91

Begin and End. Don't use "Last", as it could be thought to be the last valid member (i.e. one before the end iterator).

102

"to the object"

108

I would say that it's more common for insert to take a value_type to insert, rather than a variadic template list to construct it. I don't mind this method existing as is, but I think you should provide the "standard" signature too.

116

"a new element"

[abrachet]

Added specialization for associative containers. Addressed review comments.

[MaskRay]

This will eventually be used in D64281.

You probably need a data structure to process symbol table/section header table/program header table. To that end, this patch adds an overlay data structure (MutableRange as the name made me puzzled) to make operations more efficient. Have you benchmarked whether the librarified llvm-objcopy will benefit from a fancy data structure like this? I'm thinking plain vectors (as is) may just meet the needs.

If you just want to make interleaved insertion/deletion efficient:

1. add section .a: O(n)
2. remove section .b: O(n)
3. add section .c: O(n)
4. remove section .d: O(n)
5. add section .e: O(n)

Note you pay the O(n) cost for each operation. If you group them (online algorithm->offline) by insertion/deletion:

a) batched insertion: 1,3,5: O(n)
b) batched deletion: 2,4: O(n)

You pay the O(n) cost just twice.

If this is going to be promoted to ADT, I think it should be justified by a second use case.

[abrachet]

Created iterator for sequence container specialization. Created Clone template parameter from non trivially copy constructable types.

[abrachet]

Thanks, @MaskRay!

You probably need a data structure to process symbol table/section header table/program header table. To that end, this patch adds an overlay data structure (MutableRange as the name made me puzzled) to make operations more efficient.

The idea here was the llvm-objcopy needs to reference the original sections/symbols etc and that such a data structure could be used to keep both the original and update or add new entries.

Have you benchmarked whether the librarified llvm-objcopy will benefit from a fancy data structure like this? I'm thinking plain vectors (as is) may just meet the needs.

Not yet. But this can keep the original entries without needing to make a copy of every single one, only the ones that get modified.

If you just want to make interleaved insertion/deletion efficient

So like cache insertion/deletion and then execute them whenever the data structure is read? Can this be done with std::transform efficiently?

(MutableRange as the name made me puzzled)

Not married to the name by any means :) Just called such because it creates a mutable layer over an immutable data structure.

[MaskRay]

In D64462#1587661, @abrachet wrote:

Thanks, @MaskRay!

You probably need a data structure to process symbol table/section header table/program header table. To that end, this patch adds an overlay data structure (MutableRange as the name made me puzzled) to make operations more efficient.

The idea here was the llvm-objcopy needs to reference the original sections/symbols etc and that such a data structure could be used to keep both the original and update or add new entries.

Have you benchmarked whether the librarified llvm-objcopy will benefit from a fancy data structure like this? I'm thinking plain vectors (as is) may just meet the needs.

Not yet. But this can keep the original entries without needing to make a copy of every single one, only the ones that get modified.

If you just want to make interleaved insertion/deletion efficient

So like cache insertion/deletion and then execute them whenever the data structure is read? Can this be done with std::transform efficiently?

(MutableRange as the name made me puzzled)

Not married to the name by any means :) Just called such because it creates a mutable layer over an immutable data structure.

Using a overlay data structure for section header table is not necessary. There are not many sections. ~50 is a cap for most applications, so O(N) isn't slow at all. In lld, orphan placement algorithm is quadratic in terms of the number of output sections. This isn't an performance issue at all. I believe ld.bfd has a similar complexity.

Speaking of the dynamic symbol table and the static symbol table. Some shared objects have an awful number of .dynsym entries, e.g. my libclangAST.so has 5000+ .dynsym entries and 7000+ .symtab entries. We do should keep an eye on its performance. IMHO as long as we don't make it O(|syms|^2) it should be fine. It is currently O(|syms| * constant).

After making llvm-objcopy a library, we may do a bunch of operations on it. As I think about it, the operations may look like:

Objcopy o;
o.addSymbol();
o.removeSymbol(); // x100
o.addSymbol(); // x100
o.addSection(); // x100
o.removeSection(); // x100
o.commit(); // actually perform the operations. Make sure at this point, aggregate the previous operations and do addSymbol() in batch, removeSymbol() in batch, addSection() in batch, and removeSection() in batch.

The time complexity will be just O(|syms|*|types of operations|) instead of O(|syms|*|operations|).

[jhenderson]

Using a overlay data structure for section header table is not necessary. There are not many sections.

Not true: llvm-objcopy can be easily used on object files, which can have tens of thousands of sections, possibly more, in real-world cases that I work with, due to -ffunction-sections/-fdata-sections, COMDATs etc. Symbols are also sometimes in the order of hundreds of thousands at least, especially in linked applications. In other words, we need to be careful about the performance trade-offs we make (though linear is probably fine if anything simpler is more complex).

I'll come back to this tomorrow. Ran out of time to look more today.

[abrachet]

Fixed bug with iterator not using Cloner.

[jhenderson]

I think you're trying to do too much in this patch. Having an idea of how it could be extended is very different from going ahead and implementing it, and I really don't see a need to add support for all the types you are currently supporting. Certainly, I think this is too big to review as is.

I know I suggested bringing it across here, but @MaskRay is probably right in that we probably need another concrete use case for this code to put it into ADT. I think it would be wise to scale it back to what is needed for the MutableObject patch series, sorry.

Rather than completely throwing this all away, maybe you should create a new patch that just keeps it tightly focused to what is needed (perhaps similar to what you had before), referencing this patch, and then abandoning this patch. Then, if someone in the future feels there's a need for a more general solution, this patch can be resurrected.

llvm/include/llvm/ADT/MutableRange.h

29

Things like this probably belong in a separate TypeTraits header or similar.

32

It might be worth adding an implementation of C++ 17's void_t to make this, is_map and is_unordered much cleaner:

template <typename T>
class is_associative<T, void_t<T::key_type>> : public std::true_type {};

llvm/include/llvm/ADT/MutableRange.h

+//===-- MutableRange.h ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the MutableRange class template which wraps
+// over a const container making it effectively mutable.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_MUTABLERANGE_H
+#define LLVM_ADT_MUTABLERANGE_H
+
+#include "STLExtras.h"
+#include "iterator.h"
+#include <algorithm>
+#include <iterator>
+#include <map>
+#include <type_traits>
+#include <unordered_map>
+#include <vector>
+
+namespace llvm {
+
+template <typename T, typename = void>
+class is_associative : public std::false_type {};
+template <typename T>
+class is_associative<
+    T, typename std::enable_if<sizeof(typename T::key_type) != 0>::type>
+    : public std::true_type {};
+
+template <typename T, typename = void> class is_map : public std::false_type {};
+template <typename T>
+class is_map<
+    T, typename std::enable_if<sizeof(typename T::mapped_type) != 0>::type>
+    : public std::true_type {};
+
+template <typename T, typename = void>
+class is_unordered : public std::false_type {};
+template <typename T>
+class is_unordered<
+    T, typename std::enable_if<sizeof(typename T::hasher) != 0>::type>
+    : public std::true_type {};
+
+template <typename T, typename = void> struct get_hasher { using type = void; };
+template <typename T>
+struct get_hasher<T, typename std::enable_if<is_unordered<T>::value>::type> {
+  using type = typename T::hasher;
+};
+
+template <typename T, typename = void> struct get_mapped_type {
+  using type = void;
+};
+template <typename T>
+struct get_mapped_type<T, typename std::enable_if<is_map<T>::value>::type> {
+  using type = typename T::mapped_type;
+};
+
+template <typename Value> static constexpr Value extract_key(Value Val) {
+  return Val;
+}
+template <typename First, typename Second>
+static constexpr First extract_key(std::pair<First, Second> Pair) {
+  return Pair.first;
+}
+
+template <typename T> struct Clone {
+  static_assert(
+      std::is_trivially_copy_constructible<T>::value,
+      "must create specialization for non trivally constructable types");
+  T operator()(const T *Other) { return T(*Other); }
+};
+
+template <typename T> struct Clone<std::unique_ptr<T>> {
+  using Ptr = std::unique_ptr<T>;
+
+  Clone<T> Cloner;
+
+  Ptr operator()(const Ptr *Other) {
+    return llvm::make_unique<T>(Cloner(Other->get()));
+  }
+};
+
+template <typename T, typename Cloner = Clone<typename T::value_type>,
+          typename = void>
+class MutableRange;
+
+/// Creates a wrapper over a const container effectively making it mutable
+/// without modifying the underlying container.
+///
+/// Specialization for non associative containers.
+///
+/// @tparam T underlying container type.
+template <typename T, typename Cloner>
+class MutableRange<T, Cloner,
+                   typename std::enable_if<!is_associative<T>::value>::type> {
+  using TIter = typename T::const_iterator;
+  using MutableT = typename std::remove_const<T>::type;
+
+  Cloner Clone;
+
+public:
+  using size_type = size_t;
+  using value_type = typename T::value_type;
+
+  static_assert(
+      std::is_base_of<std::forward_iterator_tag,
+                      typename TIter::iterator_category>::value,
+      "T::iterator does not meet the requirments of a forward iterator");
+
+  /// Describes where to find the underlying object that is pointed to
+  /// by Index.
+  struct MappingType {
+    enum Operation {
+      Original = 0, /// Index represents offset from First.
+      New           /// Index represents index into Modified.
+                    /// Is either an addition or replacement.
+    };
+    Operation Type : 1;
+    size_type Index : sizeof(void *) * 8 - 1;
+
+    MappingType(const MappingType &) = default;
+    MappingType(Operation Type, size_type Index) : Type(Type), Index(Index) {}
+
+    operator size_type() const { return Index; }
+  };
+  static_assert(sizeof(MappingType) == sizeof(void *),
+                "MappingType is too large");
+
+  const TIter UnderlyingBegin;
+  const TIter UnderlyingEnd;
+
+  std::vector<MappingType> Mappings;
+  std::vector<value_type> Modified;
+
+  const value_type &getValueFromMapping(MappingType Mapping) const {
+    if (Mapping.Type == MappingType::Original) {
+      auto Begin = UnderlyingBegin;
+      std::advance(Begin, Mapping);
+      return *Begin;
+    }
+
+    return Modified[Mapping];
+  }
+
+  value_type &insert(size_type Index) {
+    auto Begin = Mappings.begin();
+    std::advance(Begin, Index);
+    Mappings.insert(Begin, MappingType(MappingType::New, Modified.size() - 1));
+    return Modified.back();
+  }
+
+public:
+  MutableRange(const MutableRange &) = default;
+  MutableRange(MutableRange &&) = default;
+  explicit MutableRange(const T &Container)
+      : MutableRange(Container.begin(), Container.end()) {}
+  MutableRange(TIter Begin, TIter End)
+      : UnderlyingBegin(Begin), UnderlyingEnd(End) {
+    size_type Length = std::distance(Begin, End);
+    Mappings.reserve(Length);
+    size_t Count = 0;
+    auto MapBegin = Mappings.begin();
+    std::transform(MapBegin, MapBegin + Length, std::back_inserter(Mappings),
+                   [&Count](const MappingType &) {
+                     return MappingType(MappingType::Original, Count++);
+                   });
+  }
+
+  class iterator : public std::vector<MappingType>::iterator {
+    using Base = typename std::vector<MappingType>::iterator;
+    const MutableRange<T, Cloner> *Range;
+
+  public:
+    iterator(Base B, const MutableRange<T, Cloner> *Range)
+        : Base(B), Range(Range) {}
+
+    const value_type &operator*() {
+      return Range->getValueFromMapping(Base::operator*());
+    }
+  };
+
+  iterator begin() { return iterator(Mappings.begin(), this); }
+  iterator end() { return iterator(Mappings.end(), this); }
+
+  /// Returns an immutable reference to the object at Index.
+  const value_type &operator[](size_type Index) const {
+    return getValueFromMapping(Mappings[Index]);
+  }
+
+  /// Emplaces a T::value_type at a specified index.
+  template <class... Ts> value_type &emplace(size_type Index, Ts &&... Args) {
+    Modified.emplace_back(value_type(std::forward<Ts>(Args)...));
+    return insert(Index);
+  }
+
+  /// Inserts a T::value_type a specified index.
+  value_type &insert(size_type Index, value_type Value) {
+    Modified.push_back(Value);
+    return insert(Index);
+  }
+
+  /// Appends a new element to the back.
+  template <class... Ts> value_type &emplace_back(Ts &&... Args) {
+    return insert(Mappings.size(), std::forward<Ts>(Args)...);
+  }
+
+  /// Removes an element at the specified Index.
+  void erase(size_type Index) {
+    assert(Index < Mappings.size() && "Index larger than number of elements");
+    Mappings.erase(Mappings.begin() + Index);
+  }
+
+  /// Returns a mutable reference to the index at Index.
+  value_type &makeMutable(size_type Index) {
+    assert(Index < Mappings.size() && "Index larger than number of elements");
+    if (Mappings[Index].Type == MappingType::New)
+      return Modified[Mappings[Index]];
+
+    auto ToCopy = UnderlyingBegin;
+    std::advance(ToCopy, Mappings[Index]);
+    Modified.push_back(Clone(&*ToCopy));
+    Mappings[Index] = MappingType(MappingType::New, Modified.size() - 1);
+    return Modified.back();
+  }
+
+  /// Returns the MutableRange as the same type as the original collection.
+  MutableT collect() const {
+    MutableT Container;
+    std::transform(Mappings.begin(), Mappings.end(),
+                   std::back_inserter(Container),
+                   [this](const MappingType &Mapping) {
+                     return getValueFromMapping(Mapping);
+                   });
+    return Container;
+  }
+};
+
+template <typename T>
+class MutableRange<T, Clone<typename T::value_type>,
+                   typename std::enable_if<is_associative<T>::value>::type> {
+public:
+  using value_type = typename T::value_type;
+  using key_type = typename T::key_type;
+
+private:
+  static constexpr bool IsMap = is_map<T>::value;
+
+  // If this is a set use the smallest available type for the internal map.
+  using MappedType =
+      typename std::conditional<IsMap, typename get_mapped_type<T>::type,
+                                char>::type;
+
+  using TIter = typename T::const_iterator;
+  using ValueType = std::pair<key_type, MappedType>;
+
+  struct InternalRep {
+    enum { IterToOrig, OwnedValueType } Type;
+
+    union {
+      TIter Iter;
+      MappedType Value;
+    };
+
+    explicit InternalRep(TIter Iter) : Type(IterToOrig), Iter(Iter) {}
+    explicit InternalRep(ValueType Value)
+        : Type(OwnedValueType), Value(Value) {}
+    // For set like T's where their mapped_type is irrelevent.
+    InternalRep() : Type(OwnedValueType), Value(0) {}
+  };
+
+  // It isn't always valid to use an unordered_map because there might not be a
+  // specialization of std::hash. If T is unordered than it is safe to use an
+  // unordered_map internally, use its hasher as it might be a user defined
+  // hasher and not a user specialization of std::hash.
+  using InternalMapType = typename std::conditional<
+      is_unordered<T>::value,
+      std::unordered_map<key_type, InternalRep, typename get_hasher<T>::type>,
+      std::map<key_type, InternalRep>>::type;
+
+  InternalMapType Map;
+
+  template <typename MapType = InternalMapType>
+  class Iterator : public MapType::iterator {
+    using Base = typename MapType::iterator;
+
+  public:
+    Iterator(const Base &B) : Base(B) {}
+
+    template <typename Ret = value_type>
+    const typename std::enable_if<IsMap, Ret>::type &operator*() const {
+      const auto &Pair = Base::operator*();
+      if (Pair.second.Type == InternalRep::IterToOrig)
+        return *Pair.second.Iter;
+      assert(Pair.second.Type == InternalRep::OwnedValueType);
+      return std::make_pair(Pair.first, Pair.second.Value);
+    }
+
+    template <typename Ret = value_type>
+    const typename std::enable_if<!IsMap, Ret>::type &operator*() const {
+      return Base::operator*().first;
+    }
+  };
+
+public:
+  MutableRange(const MutableRange &) = default;
+  MutableRange(MutableRange &&) = default;
+  explicit MutableRange(const T &Container)
+      : MutableRange(Container.begin(), Container.end()) {}
+  MutableRange(TIter First, TIter Last) {
+    for (TIter I = First; I != Last; ++I)
+      Map.insert(std::make_pair(extract_key(*I), I));
+  }
+
+  using iterator = Iterator<InternalMapType>;
+
+  iterator begin() { return Map.begin(); }
+  iterator end() { return Map.end(); }
+
+  /// Inserts a value_type into the associative container.
+  template <typename = void>
+  void insert(const value_type &Value,
+              typename std::enable_if<!IsMap, int>::type = 0) {
+    Map.insert(std::make_pair(Value, InternalRep()));
+  }
+
+#if 0
+  template <typename = void>
+  void insert(const value_type &Value, typename std::enable_if<IsMap, int>::type = 0) {
+    Map.insert(Value.first, InternalRep(Value));
+  }
+#endif
+
+  iterator find(const key_type &Key) { return Map.find(Key); }
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_MUTABLERANGE_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   IteratorTest.cpp
   MakeUniqueTest.cpp
   MappedIteratorTest.cpp
   MapVectorTest.cpp
+  MutableRangeTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   PriorityWorklistTest.cpp

llvm/unittests/ADT/MutableRangeTest.cpp

+//===-- MutableRangeTest.cpp - MutableRange unit tests --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/MutableRange.h"
+#include "llvm/ADT/STLExtras.h"
+#include "gtest/gtest.h"
+#include <map>
+#include <set>
+#include <vector>
+
+// These could be static_assert, but it makes more sense to have the static
+// assertions in this file than MutableRange.h, at that point it might as
+// well be a TEST.
+TEST(type_traits, is_associative) {
+  EXPECT_TRUE(llvm::is_associative<std::set<int>>::value)
+      << "set is associative";
+  EXPECT_FALSE(llvm::is_associative<std::vector<int>>::value)
+      << "vector not associative";
+}
+
+class MutableRangeTest : public ::testing::Test {
+
+  void TearDown() override {
+    ASSERT_EQ(IntVec.size(), 3U) << "container was modified";
+    ASSERT_EQ(IntVec[0], 1) << "container was modified";
+    ASSERT_EQ(IntVec[1], 2) << "container was modified";
+    ASSERT_EQ(IntVec[2], 3) << "container was modified";
+  }
+
+public:
+  const std::vector<int> IntVec{1, 2, 3};
+
+  const std::set<int> IntSet{1, 2, 3};
+
+  llvm::MutableRange<decltype(IntVec)> getIntRange() {
+    return llvm::MutableRange<decltype(IntVec)>(IntVec);
+  }
+
+  llvm::MutableRange<decltype(IntSet)> getIntSetRange() {
+    return llvm::MutableRange<decltype(IntSet)>(IntSet);
+  }
+};
+
+TEST_F(MutableRangeTest, Constructor) {
+  const auto Range = getIntRange();
+
+  EXPECT_EQ(Range[0], 1) << "doesn't correctly represent underlying container";
+  EXPECT_EQ(Range[1], 2);
+  EXPECT_EQ(Range[2], 3);
+
+  llvm::MutableRange<decltype(IntVec)> ConsWithIter(IntVec.begin(),
+                                                    IntVec.end());
+
+  EXPECT_EQ(ConsWithIter[0], 1) << "these constructors should be equivalent";
+  EXPECT_EQ(ConsWithIter[1], 2);
+  EXPECT_EQ(ConsWithIter[2], 3);
+}
+
+TEST_F(MutableRangeTest, Insert) {
+  auto Range = getIntRange();
+
+  EXPECT_EQ(Range.insert(1, 9), 9)
+      << "didn't correctly return reference to inserted";
+
+  EXPECT_EQ(Range[0], 1);
+  EXPECT_EQ(Range[1], 9) << "inserted in wrong area";
+  EXPECT_EQ(Range[2], 2);
+  EXPECT_EQ(Range[3], 3);
+
+  EXPECT_EQ(Range.emplace_back(4), 4)
+      << "didn't correctly return reference to appened element";
+
+  EXPECT_EQ(Range[0], 1);
+  EXPECT_EQ(Range[1], 9);
+  EXPECT_EQ(Range[2], 2);
+  EXPECT_EQ(Range[3], 3);
+  EXPECT_EQ(Range[4], 4) << "emplace_back didn't push to back";
+}
+
+TEST_F(MutableRangeTest, Erase) {
+  auto Range = getIntRange();
+
+  Range.erase(0);
+
+  EXPECT_EQ(Range[0], 2);
+  EXPECT_EQ(Range[1], 3) << "erase didn't correctly remove the element";
+}
+
+TEST_F(MutableRangeTest, MakeMutable) {
+  auto Range = getIntRange();
+
+  Range.makeMutable(0) = 10;
+
+  EXPECT_EQ(Range[0], 10) << "makeMutable didn't correctly update";
+  EXPECT_EQ(Range[1], 2);
+  EXPECT_EQ(Range[2], 3);
+}
+
+TEST_F(MutableRangeTest, Collect) {
+  auto Range = getIntRange();
+
+  Range.emplace_back(7);
+
+  std::vector<int> NewVec = Range.collect();
+
+  EXPECT_EQ(NewVec.size(), 4U);
+  EXPECT_EQ(NewVec[0], 1);
+  EXPECT_EQ(NewVec[1], 2);
+  EXPECT_EQ(NewVec[2], 3);
+  EXPECT_EQ(NewVec[3], 7);
+}
+
+TEST_F(MutableRangeTest, Iterator) {
+  auto Range = getIntRange();
+
+  int CurrentExpect = 1;
+  for (const auto &I : Range)
+    EXPECT_EQ(I, CurrentExpect++);
+}
+
+TEST_F(MutableRangeTest, NonTrivallyCopyable) {
+  std::vector<std::unique_ptr<int>> Vec;
+  Vec.push_back(llvm::make_unique<int>(1));
+  Vec.push_back(llvm::make_unique<int>(2));
+  Vec.push_back(llvm::make_unique<int>(3));
+
+  llvm::MutableRange<decltype(Vec)> Range(Vec);
+
+  EXPECT_EQ(*Range[1], 2);
+
+  Range.makeMutable(1) = llvm::make_unique<int>(5);
+
+  EXPECT_EQ(*Range[1], 5);
+
+  struct Base {
+    virtual ~Base() {}
+    virtual std::unique_ptr<Base> clone() const = 0;
+    virtual void update(int) = 0;
+    virtual int get() const { return -1; }
+  };
+
+  struct Derived : public Base {
+    int A;
+
+    Derived(int A) : A(A) {}
+
+    std::unique_ptr<Base> clone() const override {
+      return llvm::make_unique<Derived>(*this);
+    }
+
+    int get() const override { return A; }
+
+    void update(int New) override { A = New; }
+  };
+
+  struct UniquePtrBaseCloner {
+    std::unique_ptr<Base> operator()(const std::unique_ptr<Base> *Other) {
+      return (*Other)->clone();
+    }
+  };
+
+  std::vector<std::unique_ptr<Base>> NonTrivallyCopyVec;
+  NonTrivallyCopyVec.push_back(llvm::make_unique<Derived>(4));
+
+  EXPECT_EQ(NonTrivallyCopyVec[0]->get(), 4);
+
+  llvm::MutableRange<decltype(NonTrivallyCopyVec), UniquePtrBaseCloner>
+      NonTrivallyCopyRange(NonTrivallyCopyVec);
+
+  NonTrivallyCopyRange.makeMutable(0)->update(5);
+
+  EXPECT_EQ(NonTrivallyCopyRange[0]->get(), 5);
+
+  EXPECT_EQ(NonTrivallyCopyVec[0]->get(), 4);
+}
+
+TEST_F(MutableRangeTest, Set) {
+  auto Range = getIntSetRange();
+
+  EXPECT_EQ(std::distance(Range.begin(), Range.end()), 3U);
+
+  Range.insert(5);
+
+  EXPECT_EQ(std::distance(Range.begin(), Range.end()), 4U);
+
+  auto Five = Range.begin();
+  std::advance(Five, 3);
+  EXPECT_EQ(*Five, 5);
+
+  auto FoundFive = Range.find(5);
+  EXPECT_EQ(Five, FoundFive);
+}
+
+// Not currently working with map like containers.
+#if 0
+TEST_F(MutableRangeTest, Map) {
+  std::map<int, int> Map {{1, 2}, {2, 3}, {3, 4}};
+  llvm::MutableRange<decltype(Map)> Range(Map);
+
+  auto Found = Range.find(2);
+  EXPECT_EQ(Found->first, 2);
+  EXPECT_EQ(Found->second, 3);
+}
+#endif