Index: llvm/include/llvm/Support/UpdatableRange.h
===================================================================
--- /dev/null
+++ llvm/include/llvm/Support/UpdatableRange.h
@@ -0,0 +1,106 @@
+#include "llvm/ADT/SmallVector.h"
+#include <iterator>
+#include <type_traits>
+#include <vector>
+
+namespace llvm {
+
+template <typename T> class UpdatableRangeBase {
+protected:
+  using Iter = T;
+  using ValueType = typename T::value_type;
+
+  const Iter Start;
+  const Iter End;
+
+public:
+  UpdatableRangeBase() = delete;
+  UpdatableRangeBase(const UpdatableRangeBase &) = default;
+  UpdatableRangeBase(UpdatableRangeBase &&) = default;
+  UpdatableRangeBase(Iter Start, Iter End) : Start(Start), End(End) {}
+};
+
+template <typename IterTag> class is_random_access : public std::false_type {};
+template <>
+class is_random_access<std::random_access_iterator_tag>
+    : public std::true_type {};
+
+/// Creates a wrapper over a const container effectively making it mutable
+/// without modifying the underlying container.
+/// Specialization for random access iterators. Such iterators have an
+/// operator+(size_t) with constant complexity.
+/// @tparam T iterator.
+/// @tparam KeyType type of index to use.
+template <
+    typename T, typename KeyType = uint64_t,
+    typename std::enable_if<
+        is_random_access<typename T::iterator_category>::value, int>::type = 0>
+class UpdatableRange : UpdatableRangeBase<T> {
+  static_assert(std::is_integral<KeyType>::value, "expected integral KeyType");
+
+  using Iter = typename UpdatableRangeBase<T>::Iter;
+  using ValueType = typename UpdatableRangeBase<T>::ValueType;
+
+  /// Describes where to find the underlying object that is pointed to
+  /// by Index.
+  struct MappingType {
+    enum Operation {
+      Original = 0, // Index represents offset from Start.
+      Removed,      // Index not meaningful.
+      New           // Index represents index into Modified.
+                    // Is either an addition or replacment.
+    };
+    Operation Type : 2;
+    KeyType Index : sizeof(void *) * 8 - 2;
+
+    MappingType(Operation Type, KeyType Index) : Type(Type), Index(Index) {}
+
+    operator KeyType() { return Index; }
+  };
+
+  std::vector<MappingType> Mappings;
+  std::vector<ValueType> Modified;
+
+public:
+  UpdatableRange() = delete;
+  UpdatableRange(const UpdatableRange &) = default;
+  UpdatableRange(UpdatableRange &&) = default;
+  UpdatableRange(Iter Start, Iter End) : UpdatableRangeBase<T>(Start, End) {
+    auto Length = std::distance(Start, End);
+    Mappings.reserve(Length);
+    for (int I = 0; I < Length; ++I)
+      Mappings.push_back(MappingType(MappingType::Original, I));
+  }
+
+  const ValueType &operator[](KeyType Index) {
+    if (Mappings[Index].Type == MappingType::Original)
+      return *(this->Start + Mappings[Index]);
+    return Modified[Mappings[Index]];
+  }
+
+  /// Emplaces a T::value_type at a specified index
+  template <class... Ts> ValueType &insert(KeyType Index, Ts &&... Args) {
+    Modified.emplace_back(ValueType(std::forward<Ts>(Args)...));
+    Mappings.insert(Mappings.begin() + Index,
+                    MappingType(MappingType::New, Modified.size() - 1));
+    return Modified.back();
+  }
+
+  template <class... Ts> ValueType &emplace_back(Ts &&... Args) {
+    return insert(Mappings.size(), std::forward<Ts>(Args)...);
+  }
+
+  /// Returns a mutable reference to the index at Index.
+  ValueType &makeMutable(KeyType Index) {
+    assert(Mappings[Index].Type != MappingType::Removed &&
+           "Element was removed");
+    if (Mappings[Index].Type == MappingType::New)
+      return Modified[Mappings[Index]];
+
+    Modified.emplace_back(ValueType(this->Start[Mappings[Index]]));
+    Mappings[Index] = MappingType(MappingType::New, Modified.size() - 1);
+    return Modified.back();
+  }
+};
+
+} // namespace llvm
Index: llvm/unittests/Support/CMakeLists.txt
===================================================================
--- llvm/unittests/Support/CMakeLists.txt
+++ llvm/unittests/Support/CMakeLists.txt
@@ -72,6 +72,7 @@
   TrailingObjectsTest.cpp
   TrigramIndexTest.cpp
   UnicodeTest.cpp
+  UpdatableRangeTest.cpp
   VersionTupleTest.cpp
   VirtualFileSystemTest.cpp
   YAMLIOTest.cpp
Index: llvm/unittests/Support/UpdatableRangeTest.cpp
===================================================================
--- /dev/null
+++ llvm/unittests/Support/UpdatableRangeTest.cpp
@@ -0,0 +1,41 @@
+
+#include "llvm/Support/UpdatableRange.h"
+#include "gtest/gtest.h"
+#include <vector>
+
+TEST(Basic, Test) {
+  const std::vector<int> Vec {1, 2, 3};
+
+  llvm::UpdatableRange<decltype(Vec.begin())> Range(Vec.begin(), Vec.end());
+
+  EXPECT_EQ(Range[0], 1) << "doesn't correctly represent underlying container";
+  EXPECT_EQ(Range[1], 2);
+  EXPECT_EQ(Range[2], 3);
+
+  EXPECT_EQ(Range.insert(1, 9), 9);
+
+  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);
+
+  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";
+
+  Range.makeMutable(0) = 2;
+
+  EXPECT_EQ(Range[0], 2) << "makeMutable didn't correctly update";
+  EXPECT_EQ(Range[1], 9);
+  EXPECT_EQ(Range[2], 2);
+  EXPECT_EQ(Range[3], 3);
+  EXPECT_EQ(Range[4], 4);
+
+  EXPECT_EQ(Vec[0], 1) << "const not respected on underlying container";
+  EXPECT_EQ(Vec[1], 2);
+  EXPECT_EQ(Vec[2], 3);
+}