Index: llvm/include/llvm/ADT/MutableRange.h
===================================================================
--- /dev/null
+++ llvm/include/llvm/ADT/MutableRange.h
@@ -0,0 +1,342 @@
+//===-- 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
Index: llvm/unittests/ADT/CMakeLists.txt
===================================================================
--- llvm/unittests/ADT/CMakeLists.txt
+++ llvm/unittests/ADT/CMakeLists.txt
@@ -39,6 +39,7 @@
   MakeUniqueTest.cpp
   MappedIteratorTest.cpp
   MapVectorTest.cpp
+  MutableRangeTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
Index: llvm/unittests/ADT/MutableRangeTest.cpp
===================================================================
--- /dev/null
+++ llvm/unittests/ADT/MutableRangeTest.cpp
@@ -0,0 +1,209 @@
+//===-- 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