Initial Commit

8 files changed, 4567 insertions, 0 deletions

diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
new file mode 100644
index 000000000000..625cef106fc5
--- /dev/null
+++ b/absl/container/BUILD.bazel
@@ -0,0 +1,124 @@
+#
+# Copyright 2017 The Abseil Authors.
+#
+# 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.
+#
+
+load(
+    "//absl:copts.bzl",
+    "ABSL_DEFAULT_COPTS",
+    "ABSL_TEST_COPTS",
+)
+load(
+    "//absl:test_dependencies.bzl",
+    "GUNIT_MAIN_DEPS_SELECTOR",
+)
+
+package(default_visibility = ["//visibility:public"])
+
+licenses(["notice"])  # Apache 2.0
+
+cc_library(
+    name = "fixed_array",
+    hdrs = ["fixed_array.h"],
+    copts = ABSL_DEFAULT_COPTS,
+    deps = [
+        "//absl/algorithm",
+        "//absl/base:core_headers",
+        "//absl/base:dynamic_annotations",
+        "//absl/base:throw_delegate",
+    ],
+)
+
+cc_test(
+    name = "fixed_array_test",
+    srcs = ["fixed_array_test.cc"],
+    copts = ABSL_TEST_COPTS + ["-fexceptions"],
+    deps = [
+        ":fixed_array",
+        "//absl/base:core_headers",
+        "//absl/base:exception_testing",
+        "//absl/memory",
+    ] + select(GUNIT_MAIN_DEPS_SELECTOR),
+)
+
+cc_test(
+    name = "fixed_array_test_noexceptions",
+    srcs = ["fixed_array_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    deps = [
+        ":fixed_array",
+        "//absl/base:core_headers",
+        "//absl/base:exception_testing",
+        "//absl/memory",
+    ] + select(GUNIT_MAIN_DEPS_SELECTOR),
+)
+
+cc_library(
+    name = "inlined_vector",
+    hdrs = ["inlined_vector.h"],
+    copts = ABSL_DEFAULT_COPTS,
+    deps = [
+        "//absl/algorithm",
+        "//absl/base:core_headers",
+        "//absl/base:throw_delegate",
+        "//absl/memory",
+    ],
+)
+
+cc_test(
+    name = "inlined_vector_test",
+    srcs = ["inlined_vector_test.cc"],
+    copts = ABSL_TEST_COPTS + ["-fexceptions"],
+    deps = [
+        ":inlined_vector",
+        ":test_instance_tracker",
+        "//absl/base",
+        "//absl/base:core_headers",
+        "//absl/base:exception_testing",
+        "//absl/memory",
+        "//absl/strings",
+    ] + select(GUNIT_MAIN_DEPS_SELECTOR),
+)
+
+cc_test(
+    name = "inlined_vector_test_noexceptions",
+    srcs = ["inlined_vector_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    deps = [
+        ":inlined_vector",
+        ":test_instance_tracker",
+        "//absl/base",
+        "//absl/base:core_headers",
+        "//absl/base:exception_testing",
+        "//absl/memory",
+        "//absl/strings",
+    ] + select(GUNIT_MAIN_DEPS_SELECTOR),
+)
+
+cc_library(
+    name = "test_instance_tracker",
+    testonly = 1,
+    srcs = ["internal/test_instance_tracker.cc"],
+    hdrs = ["internal/test_instance_tracker.h"],
+    copts = ABSL_DEFAULT_COPTS,
+)
+
+cc_test(
+    name = "test_instance_tracker_test",
+    srcs = ["internal/test_instance_tracker_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    deps = [
+        ":test_instance_tracker",
+    ] + select(GUNIT_MAIN_DEPS_SELECTOR),
+)
diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h
new file mode 100644
index 000000000000..20bde27285b8
--- /dev/null
+++ b/absl/container/fixed_array.h
@@ -0,0 +1,493 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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.
+//
+// -----------------------------------------------------------------------------
+// File: fixed_array.h
+// -----------------------------------------------------------------------------
+//
+// A `FixedArray<T>` represents a non-resizable array of `T` where the length of
+// the array can be determined at run-time. It is a good replacement for
+// non-standard and deprecated uses of `alloca()` and variable length arrays
+// within the GCC extension. (See
+// https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html).
+//
+// `FixedArray` allocates small arrays inline, keeping performance fast by
+// avoiding heap operations. It also helps reduce the chances of
+// accidentally overflowing your stack if large input is passed to
+// your function.
+
+#ifndef ABSL_CONTAINER_FIXED_ARRAY_H_
+#define ABSL_CONTAINER_FIXED_ARRAY_H_
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <initializer_list>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <new>
+#include <type_traits>
+
+#include "absl/algorithm/algorithm.h"
+#include "absl/base/dynamic_annotations.h"
+#include "absl/base/internal/throw_delegate.h"
+#include "absl/base/macros.h"
+#include "absl/base/optimization.h"
+#include "absl/base/port.h"
+
+namespace absl {
+
+constexpr static auto kFixedArrayUseDefault = static_cast<size_t>(-1);
+
+// -----------------------------------------------------------------------------
+// FixedArray
+// -----------------------------------------------------------------------------
+//
+// A `FixedArray` provides a run-time fixed-size array, allocating small arrays
+// inline for efficiency and correctness.
+//
+// Most users should not specify an `inline_elements` argument and let
+// `FixedArray<>` automatically determine the number of elements
+// to store inline based on `sizeof(T)`. If `inline_elements` is specified, the
+// `FixedArray<>` implementation will inline arrays of
+// length <= `inline_elements`.
+//
+// Note that a `FixedArray` constructed with a `size_type` argument will
+// default-initialize its values by leaving trivially constructible types
+// uninitialized (e.g. int, int[4], double), and others default-constructed.
+// This matches the behavior of c-style arrays and `std::array`, but not
+// `std::vector`.
+//
+// Note that `FixedArray` does not provide a public allocator; if it requires a
+// heap allocation, it will do so with global `::operator new[]()` and
+// `::operator delete[]()`, even if T provides class-scope overrides for these
+// operators.
+template <typename T, size_t inlined = kFixedArrayUseDefault>
+class FixedArray {
+  static constexpr size_t kInlineBytesDefault = 256;
+
+  // std::iterator_traits isn't guaranteed to be SFINAE-friendly until C++17,
+  // but this seems to be mostly pedantic.
+  template <typename Iter>
+  using EnableIfForwardIterator = typename std::enable_if<
+      std::is_convertible<
+          typename std::iterator_traits<Iter>::iterator_category,
+          std::forward_iterator_tag>::value,
+      int>::type;
+
+ public:
+  // For playing nicely with stl:
+  using value_type = T;
+  using iterator = T*;
+  using const_iterator = const T*;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  using reference = T&;
+  using const_reference = const T&;
+  using pointer = T*;
+  using const_pointer = const T*;
+  using difference_type = ptrdiff_t;
+  using size_type = size_t;
+
+  static constexpr size_type inline_elements =
+      inlined == kFixedArrayUseDefault
+          ? kInlineBytesDefault / sizeof(value_type)
+          : inlined;
+
+  // Creates an array object that can store `n` elements.
+  // Note that trivially constructible elements will be uninitialized.
+  explicit FixedArray(size_type n) : rep_(n) {}
+
+  // Creates an array initialized with `n` copies of `val`.
+  FixedArray(size_type n, const value_type& val) : rep_(n, val) {}
+
+  // Creates an array initialized with the elements from the input
+  // range. The array's size will always be `std::distance(first, last)`.
+  // REQUIRES: Iter must be a forward_iterator or better.
+  template <typename Iter, EnableIfForwardIterator<Iter> = 0>
+  FixedArray(Iter first, Iter last) : rep_(first, last) {}
+
+  // Create the array from an initializer_list.
+  FixedArray(std::initializer_list<T> init_list)
+      : FixedArray(init_list.begin(), init_list.end()) {}
+
+  ~FixedArray() {}
+
+  // Copy and move construction and assignment are deleted because (1) you can't
+  // copy or move an array, (2) assignment breaks the invariant that the size of
+  // a `FixedArray` never changes, and (3) there's no clear answer as to what
+  // should happen to a moved-from `FixedArray`.
+  FixedArray(const FixedArray&) = delete;
+  void operator=(const FixedArray&) = delete;
+
+  // FixedArray::size()
+  //
+  // Returns the length of the fixed array.
+  size_type size() const { return rep_.size(); }
+
+  // FixedArray::max_size()
+  //
+  // Returns the largest possible value of `std::distance(begin(), end())` for a
+  // `FixedArray<T>`. This is equivalent to the most possible addressable bytes
+  // over the number of bytes taken by T.
+  constexpr size_type max_size() const {
+    return std::numeric_limits<difference_type>::max() / sizeof(value_type);
+  }
+
+  // FixedArray::empty()
+  //
+  // Returns whether or not the fixed array is empty.
+  bool empty() const { return size() == 0; }
+
+  // FixedArray::memsize()
+  //
+  // Returns the memory size of the fixed array in bytes.
+  size_t memsize() const { return size() * sizeof(value_type); }
+
+  // FixedArray::data()
+  //
+  // Returns a const T* pointer to elements of the `FixedArray`. This pointer
+  // can be used to access (but not modify) the contained elements.
+  const_pointer data() const { return AsValue(rep_.begin()); }
+
+  // Overload of FixedArray::data() to return a T* pointer to elements of the
+  // fixed array. This pointer can be used to access and modify the contained
+  // elements.
+  pointer data() { return AsValue(rep_.begin()); }
+  // FixedArray::operator[]
+  //
+  // Returns a reference the ith element of the fixed array.
+  // REQUIRES: 0 <= i < size()
+  reference operator[](size_type i) {
+    assert(i < size());
+    return data()[i];
+  }
+
+  // Overload of FixedArray::operator()[] to return a const reference to the
+  // ith element of the fixed array.
+  // REQUIRES: 0 <= i < size()
+  const_reference operator[](size_type i) const {
+    assert(i < size());
+    return data()[i];
+  }
+
+  // FixedArray::at
+  //
+  // Bounds-checked access.  Returns a reference to the ith element of the
+  // fiexed array, or throws std::out_of_range
+  reference at(size_type i) {
+    if (ABSL_PREDICT_FALSE(i >= size())) {
+      base_internal::ThrowStdOutOfRange("FixedArray::at failed bounds check");
+    }
+    return data()[i];
+  }
+
+  // Overload of FixedArray::at() to return a const reference to the ith element
+  // of the fixed array.
+  const_reference at(size_type i) const {
+    if (i >= size()) {
+      base_internal::ThrowStdOutOfRange("FixedArray::at failed bounds check");
+    }
+    return data()[i];
+  }
+
+  // FixedArray::front()
+  //
+  // Returns a reference to the first element of the fixed array.
+  reference front() { return *begin(); }
+
+  // Overload of FixedArray::front() to return a reference to the first element
+  // of a fixed array of const values.
+  const_reference front() const { return *begin(); }
+
+  // FixedArray::back()
+  //
+  // Returns a reference to the last element of the fixed array.
+  reference back() { return *(end() - 1); }
+
+  // Overload of FixedArray::back() to return a reference to the last element
+  // of a fixed array of const values.
+  const_reference back() const { return *(end() - 1); }
+
+  // FixedArray::begin()
+  //
+  // Returns an iterator to the beginning of the fixed array.
+  iterator begin() { return data(); }
+
+  // Overload of FixedArray::begin() to return a const iterator to the
+  // beginning of the fixed array.
+  const_iterator begin() const { return data(); }
+
+  // FixedArray::cbegin()
+  //
+  // Returns a const iterator to the beginning of the fixed array.
+  const_iterator cbegin() const { return begin(); }
+
+  // FixedArray::end()
+  //
+  // Returns an iterator to the end of the fixed array.
+  iterator end() { return data() + size(); }
+
+  // Overload of FixedArray::end() to return a const iterator to the end of the
+  // fixed array.
+  const_iterator end() const { return data() + size(); }
+
+  // FixedArray::cend()
+  //
+  // Returns a const iterator to the end of the fixed array.
+  const_iterator cend() const { return end(); }
+
+  // FixedArray::rbegin()
+  //
+  // Returns a reverse iterator from the end of the fixed array.
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+
+  // Overload of FixedArray::rbegin() to return a const reverse iterator from
+  // the end of the fixed array.
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+
+  // FixedArray::crbegin()
+  //
+  // Returns a const reverse iterator from the end of the fixed array.
+  const_reverse_iterator crbegin() const { return rbegin(); }
+
+  // FixedArray::rend()
+  //
+  // Returns a reverse iterator from the beginning of the fixed array.
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+
+  // Overload of FixedArray::rend() for returning a const reverse iterator
+  // from the beginning of the fixed array.
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
+
+  // FixedArray::crend()
+  //
+  // Returns a reverse iterator from the beginning of the fixed array.
+  const_reverse_iterator crend() const { return rend(); }
+
+  // FixedArray::fill()
+  //
+  // Assigns the given `value` to all elements in the fixed array.
+  void fill(const T& value) { std::fill(begin(), end(), value); }
+
+  // Relational operators. Equality operators are elementwise using
+  // `operator==`, while order operators order FixedArrays lexicographically.
+  friend bool operator==(const FixedArray& lhs, const FixedArray& rhs) {
+    return absl::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+  }
+
+  friend bool operator!=(const FixedArray& lhs, const FixedArray& rhs) {
+    return !(lhs == rhs);
+  }
+
+  friend bool operator<(const FixedArray& lhs, const FixedArray& rhs) {
+    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
+                                        rhs.end());
+  }
+
+  friend bool operator>(const FixedArray& lhs, const FixedArray& rhs) {
+    return rhs < lhs;
+  }
+
+  friend bool operator<=(const FixedArray& lhs, const FixedArray& rhs) {
+    return !(rhs < lhs);
+  }
+
+  friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) {
+    return !(lhs < rhs);
+  }
+
+ private:
+  // HolderTraits
+  //
+  // Wrapper to hold elements of type T for the case where T is an array type.
+  // If 'T' is an array type, HolderTraits::type is a struct with a 'T v;'.
+  // Otherwise, HolderTraits::type is simply 'T'.
+  //
+  // Maintainer's Note: The simpler solution would be to simply wrap T in a
+  // struct whether it's an array or not: 'struct Holder { T v; };', but
+  // that causes some paranoid diagnostics to misfire about uses of data(),
+  // believing that 'data()' (aka '&rep_.begin().v') is a pointer to a single
+  // element, rather than the packed array that it really is.
+  // e.g.:
+  //
+  //     FixedArray<char> buf(1);
+  //     sprintf(buf.data(), "foo");
+  //
+  //     error: call to int __builtin___sprintf_chk(etc...)
+  //     will always overflow destination buffer [-Werror]
+  //
+  class HolderTraits {
+    template <typename U>
+    struct SelectImpl {
+      using type = U;
+      static pointer AsValue(type* p) { return p; }
+    };
+
+    // Partial specialization for elements of array type.
+    template <typename U, size_t N>
+    struct SelectImpl<U[N]> {
+      struct Holder { U v[N]; };
+      using type = Holder;
+      static pointer AsValue(type* p) { return &p->v; }
+    };
+    using Impl = SelectImpl<value_type>;
+
+   public:
+    using type = typename Impl::type;
+
+    static pointer AsValue(type *p) { return Impl::AsValue(p); }
+
+    // TODO(billydonahue): fix the type aliasing violation
+    // this assertion hints at.
+    static_assert(sizeof(type) == sizeof(value_type),
+                  "Holder must be same size as value_type");
+  };
+
+  using Holder = typename HolderTraits::type;
+  static pointer AsValue(Holder *p) { return HolderTraits::AsValue(p); }
+
+  // InlineSpace
+  //
+  // Allocate some space, not an array of elements of type T, so that we can
+  // skip calling the T constructors and destructors for space we never use.
+  // How many elements should we store inline?
+  //   a. If not specified, use a default of kInlineBytesDefault bytes (This is
+  //   currently 256 bytes, which seems small enough to not cause stack overflow
+  //   or unnecessary stack pollution, while still allowing stack allocation for
+  //   reasonably long character arrays).
+  //   b. Never use 0 length arrays (not ISO C++)
+  //
+  template <size_type N, typename = void>
+  class InlineSpace {
+   public:
+    Holder* data() { return reinterpret_cast<Holder*>(space_.data()); }
+    void AnnotateConstruct(size_t n) const { Annotate(n, true); }
+    void AnnotateDestruct(size_t n) const { Annotate(n, false); }
+
+   private:
+#ifndef ADDRESS_SANITIZER
+    void Annotate(size_t, bool) const { }
+#else
+    void Annotate(size_t n, bool creating) const {
+      if (!n) return;
+      const void* bot = &left_redzone_;
+      const void* beg = space_.data();
+      const void* end = space_.data() + n;
+      const void* top = &right_redzone_ + 1;
+      // args: (beg, end, old_mid, new_mid)
+      if (creating) {
+        ANNOTATE_CONTIGUOUS_CONTAINER(beg, top, top, end);
+        ANNOTATE_CONTIGUOUS_CONTAINER(bot, beg, beg, bot);
+      } else {
+        ANNOTATE_CONTIGUOUS_CONTAINER(beg, top, end, top);
+        ANNOTATE_CONTIGUOUS_CONTAINER(bot, beg, bot, beg);
+      }
+    }
+#endif  // ADDRESS_SANITIZER
+
+    using Buffer =
+        typename std::aligned_storage<sizeof(Holder), alignof(Holder)>::type;
+
+    ADDRESS_SANITIZER_REDZONE(left_redzone_);
+    std::array<Buffer, N> space_;
+    ADDRESS_SANITIZER_REDZONE(right_redzone_);
+  };
+
+  // specialization when N = 0.
+  template <typename U>
+  class InlineSpace<0, U> {
+   public:
+    Holder* data() { return nullptr; }
+    void AnnotateConstruct(size_t) const {}
+    void AnnotateDestruct(size_t) const {}
+  };
+
+  // Rep
+  //
+  // A const Rep object holds FixedArray's size and data pointer.
+  //
+  class Rep : public InlineSpace<inline_elements> {
+   public:
+    Rep(size_type n, const value_type& val) : n_(n), p_(MakeHolder(n)) {
+      std::uninitialized_fill_n(p_, n, val);
+    }
+
+    explicit Rep(size_type n) : n_(n), p_(MakeHolder(n)) {
+      // Loop optimizes to nothing for trivially constructible T.
+      for (Holder* p = p_; p != p_ + n; ++p)
+        // Note: no parens: default init only.
+        // Also note '::' to avoid Holder class placement new operator.
+        ::new (static_cast<void*>(p)) Holder;
+    }
+
+    template <typename Iter>
+    Rep(Iter first, Iter last)
+        : n_(std::distance(first, last)), p_(MakeHolder(n_)) {
+      std::uninitialized_copy(first, last, AsValue(p_));
+    }
+
+    ~Rep() {
+      // Destruction must be in reverse order.
+      // Loop optimizes to nothing for trivially destructible T.
+      for (Holder* p = end(); p != begin();) (--p)->~Holder();
+      if (IsAllocated(size())) {
+        ::operator delete[](begin());
+      } else {
+        this->AnnotateDestruct(size());
+      }
+    }
+    Holder* begin() const { return p_; }
+    Holder* end() const { return p_ + n_; }
+    size_type size() const { return n_; }
+
+   private:
+    Holder* MakeHolder(size_type n) {
+      if (IsAllocated(n)) {
+        return Allocate(n);
+      } else {
+        this->AnnotateConstruct(n);
+        return this->data();
+      }
+    }
+
+    Holder* Allocate(size_type n) {
+      return static_cast<Holder*>(::operator new[](n * sizeof(Holder)));
+    }
+
+    bool IsAllocated(size_type n) const { return n > inline_elements; }
+
+    const size_type n_;
+    Holder* const p_;
+  };
+
+
+  // Data members
+  Rep rep_;
+};
+
+template <typename T, size_t N>
+constexpr size_t FixedArray<T, N>::inline_elements;
+
+template <typename T, size_t N>
+constexpr size_t FixedArray<T, N>::kInlineBytesDefault;
+
+}  // namespace absl
+#endif  // ABSL_CONTAINER_FIXED_ARRAY_H_
diff --git a/absl/container/fixed_array_test.cc b/absl/container/fixed_array_test.cc
new file mode 100644
index 000000000000..9e88eab0c696
--- /dev/null
+++ b/absl/container/fixed_array_test.cc
@@ -0,0 +1,621 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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 "absl/container/fixed_array.h"
+
+#include <stdio.h>
+#include <list>
+#include <memory>
+#include <numeric>
+#include <stdexcept>
+#include <string>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/internal/exception_testing.h"
+#include "absl/memory/memory.h"
+
+namespace {
+
+// Helper routine to determine if a absl::FixedArray used stack allocation.
+template <typename ArrayType>
+static bool IsOnStack(const ArrayType& a) {
+  return a.size() <= ArrayType::inline_elements;
+}
+
+class ConstructionTester {
+ public:
+  ConstructionTester()
+      : self_ptr_(this),
+        value_(0) {
+    constructions++;
+  }
+  ~ConstructionTester() {
+    assert(self_ptr_ == this);
+    self_ptr_ = nullptr;
+    destructions++;
+  }
+
+  // These are incremented as elements are constructed and destructed so we can
+  // be sure all elements are properly cleaned up.
+  static int constructions;
+  static int destructions;
+
+  void CheckConstructed() {
+    assert(self_ptr_ == this);
+  }
+
+  void set(int value) { value_ = value; }
+  int get() { return value_; }
+
+ private:
+  // self_ptr_ should always point to 'this' -- that's how we can be sure the
+  // constructor has been called.
+  ConstructionTester* self_ptr_;
+  int value_;
+};
+
+int ConstructionTester::constructions = 0;
+int ConstructionTester::destructions = 0;
+
+// ThreeInts will initialize its three ints to the value stored in
+// ThreeInts::counter. The constructor increments counter so that each object
+// in an array of ThreeInts will have different values.
+class ThreeInts {
+ public:
+  ThreeInts() {
+    x_ = counter;
+    y_ = counter;
+    z_ = counter;
+    ++counter;
+  }
+
+  static int counter;
+
+  int x_, y_, z_;
+};
+
+int ThreeInts::counter = 0;
+
+TEST(FixedArrayTest, SmallObjects) {
+  // Small object arrays
+  {
+    // Short arrays should be on the stack
+    absl::FixedArray<int> array(4);
+    EXPECT_TRUE(IsOnStack(array));
+  }
+
+  {
+    // Large arrays should be on the heap
+    absl::FixedArray<int> array(1048576);
+    EXPECT_FALSE(IsOnStack(array));
+  }
+
+  {
+    // Arrays of <= default size should be on the stack
+    absl::FixedArray<int, 100> array(100);
+    EXPECT_TRUE(IsOnStack(array));
+  }
+
+  {
+    // Arrays of > default size should be on the stack
+    absl::FixedArray<int, 100> array(101);
+    EXPECT_FALSE(IsOnStack(array));
+  }
+
+  {
+    // Arrays with different size elements should use approximately
+    // same amount of stack space
+    absl::FixedArray<int> array1(0);
+    absl::FixedArray<char> array2(0);
+    EXPECT_LE(sizeof(array1), sizeof(array2)+100);
+    EXPECT_LE(sizeof(array2), sizeof(array1)+100);
+  }
+
+  {
+    // Ensure that vectors are properly constructed inside a fixed array.
+    absl::FixedArray<std::vector<int> > array(2);
+    EXPECT_EQ(0, array[0].size());
+    EXPECT_EQ(0, array[1].size());
+  }
+
+  {
+    // Regardless of absl::FixedArray implementation, check that a type with a
+    // low alignment requirement and a non power-of-two size is initialized
+    // correctly.
+    ThreeInts::counter = 1;
+    absl::FixedArray<ThreeInts> array(2);
+    EXPECT_EQ(1, array[0].x_);
+    EXPECT_EQ(1, array[0].y_);
+    EXPECT_EQ(1, array[0].z_);
+    EXPECT_EQ(2, array[1].x_);
+    EXPECT_EQ(2, array[1].y_);
+    EXPECT_EQ(2, array[1].z_);
+  }
+}
+
+TEST(FixedArrayTest, AtThrows) {
+  absl::FixedArray<int> a = {1, 2, 3};
+  EXPECT_EQ(a.at(2), 3);
+  ABSL_BASE_INTERNAL_EXPECT_FAIL(a.at(3), std::out_of_range,
+                                 "failed bounds check");
+}
+
+TEST(FixedArrayRelationalsTest, EqualArrays) {
+  for (int i = 0; i < 10; ++i) {
+    absl::FixedArray<int, 5> a1(i);
+    std::iota(a1.begin(), a1.end(), 0);
+    absl::FixedArray<int, 5> a2(a1.begin(), a1.end());
+
+    EXPECT_TRUE(a1 == a2);
+    EXPECT_FALSE(a1 != a2);
+    EXPECT_TRUE(a2 == a1);
+    EXPECT_FALSE(a2 != a1);
+    EXPECT_FALSE(a1 < a2);
+    EXPECT_FALSE(a1 > a2);
+    EXPECT_FALSE(a2 < a1);
+    EXPECT_FALSE(a2 > a1);
+    EXPECT_TRUE(a1 <= a2);
+    EXPECT_TRUE(a1 >= a2);
+    EXPECT_TRUE(a2 <= a1);
+    EXPECT_TRUE(a2 >= a1);
+  }
+}
+
+TEST(FixedArrayRelationalsTest, UnequalArrays) {
+  for (int i = 1; i < 10; ++i) {
+    absl::FixedArray<int, 5> a1(i);
+    std::iota(a1.begin(), a1.end(), 0);
+    absl::FixedArray<int, 5> a2(a1.begin(), a1.end());
+    --a2[i / 2];
+
+    EXPECT_FALSE(a1 == a2);
+    EXPECT_TRUE(a1 != a2);
+    EXPECT_FALSE(a2 == a1);
+    EXPECT_TRUE(a2 != a1);
+    EXPECT_FALSE(a1 < a2);
+    EXPECT_TRUE(a1 > a2);
+    EXPECT_TRUE(a2 < a1);
+    EXPECT_FALSE(a2 > a1);
+    EXPECT_FALSE(a1 <= a2);
+    EXPECT_TRUE(a1 >= a2);
+    EXPECT_TRUE(a2 <= a1);
+    EXPECT_FALSE(a2 >= a1);
+  }
+}
+
+template <int stack_elements>
+static void TestArray(int n) {
+  SCOPED_TRACE(n);
+  SCOPED_TRACE(stack_elements);
+  ConstructionTester::constructions = 0;
+  ConstructionTester::destructions = 0;
+  {
+    absl::FixedArray<ConstructionTester, stack_elements> array(n);
+
+    EXPECT_THAT(array.size(), n);
+    EXPECT_THAT(array.memsize(), sizeof(ConstructionTester) * n);
+    EXPECT_THAT(array.begin() + n, array.end());
+
+    // Check that all elements were constructed
+    for (int i = 0; i < n; i++) {
+      array[i].CheckConstructed();
+    }
+    // Check that no other elements were constructed
+    EXPECT_THAT(ConstructionTester::constructions, n);
+
+    // Test operator[]
+    for (int i = 0; i < n; i++) {
+      array[i].set(i);
+    }
+    for (int i = 0; i < n; i++) {
+      EXPECT_THAT(array[i].get(), i);
+      EXPECT_THAT(array.data()[i].get(), i);
+    }
+
+    // Test data()
+    for (int i = 0; i < n; i++) {
+      array.data()[i].set(i + 1);
+    }
+    for (int i = 0; i < n; i++) {
+      EXPECT_THAT(array[i].get(), i+1);
+      EXPECT_THAT(array.data()[i].get(), i+1);
+    }
+  }  // Close scope containing 'array'.
+
+  // Check that all constructed elements were destructed.
+  EXPECT_EQ(ConstructionTester::constructions,
+            ConstructionTester::destructions);
+}
+
+template <int elements_per_inner_array, int inline_elements>
+static void TestArrayOfArrays(int n) {
+  SCOPED_TRACE(n);
+  SCOPED_TRACE(inline_elements);
+  SCOPED_TRACE(elements_per_inner_array);
+  ConstructionTester::constructions = 0;
+  ConstructionTester::destructions = 0;
+  {
+    using InnerArray = ConstructionTester[elements_per_inner_array];
+    // Heap-allocate the FixedArray to avoid blowing the stack frame.
+    auto array_ptr =
+        absl::make_unique<absl::FixedArray<InnerArray, inline_elements>>(n);
+    auto& array = *array_ptr;
+
+    ASSERT_EQ(array.size(), n);
+    ASSERT_EQ(array.memsize(),
+             sizeof(ConstructionTester) * elements_per_inner_array * n);
+    ASSERT_EQ(array.begin() + n, array.end());
+
+    // Check that all elements were constructed
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < elements_per_inner_array; j++) {
+        (array[i])[j].CheckConstructed();
+      }
+    }
+    // Check that no other elements were constructed
+    ASSERT_EQ(ConstructionTester::constructions, n * elements_per_inner_array);
+
+    // Test operator[]
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < elements_per_inner_array; j++) {
+        (array[i])[j].set(i * elements_per_inner_array + j);
+      }
+    }
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < elements_per_inner_array; j++) {
+        ASSERT_EQ((array[i])[j].get(),  i * elements_per_inner_array + j);
+        ASSERT_EQ((array.data()[i])[j].get(), i * elements_per_inner_array + j);
+      }
+    }
+
+    // Test data()
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < elements_per_inner_array; j++) {
+        (array.data()[i])[j].set((i + 1) * elements_per_inner_array + j);
+      }
+    }
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < elements_per_inner_array; j++) {
+        ASSERT_EQ((array[i])[j].get(),
+                  (i + 1) * elements_per_inner_array + j);
+        ASSERT_EQ((array.data()[i])[j].get(),
+                  (i + 1) * elements_per_inner_array + j);
+      }
+    }
+  }  // Close scope containing 'array'.
+
+  // Check that all constructed elements were destructed.
+  EXPECT_EQ(ConstructionTester::constructions,
+            ConstructionTester::destructions);
+}
+
+TEST(IteratorConstructorTest, NonInline) {
+  int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+  absl::FixedArray<int, ABSL_ARRAYSIZE(kInput) - 1> const fixed(
+      kInput, kInput + ABSL_ARRAYSIZE(kInput));
+  ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
+  for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
+    ASSERT_EQ(kInput[i], fixed[i]);
+  }
+}
+
+TEST(IteratorConstructorTest, Inline) {
+  int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+  absl::FixedArray<int, ABSL_ARRAYSIZE(kInput)> const fixed(
+      kInput, kInput + ABSL_ARRAYSIZE(kInput));
+  ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
+  for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
+    ASSERT_EQ(kInput[i], fixed[i]);
+  }
+}
+
+TEST(IteratorConstructorTest, NonPod) {
+  char const* kInput[] =
+      { "red", "orange", "yellow", "green", "blue", "indigo", "violet" };
+  absl::FixedArray<std::string> const fixed(kInput, kInput + ABSL_ARRAYSIZE(kInput));
+  ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
+  for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
+    ASSERT_EQ(kInput[i], fixed[i]);
+  }
+}
+
+TEST(IteratorConstructorTest, FromEmptyVector) {
+  std::vector<int> const empty;
+  absl::FixedArray<int> const fixed(empty.begin(), empty.end());
+  EXPECT_EQ(0, fixed.size());
+  EXPECT_EQ(empty.size(), fixed.size());
+}
+
+TEST(IteratorConstructorTest, FromNonEmptyVector) {
+  int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+  std::vector<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput));
+  absl::FixedArray<int> const fixed(items.begin(), items.end());
+  ASSERT_EQ(items.size(), fixed.size());
+  for (size_t i = 0; i < items.size(); ++i) {
+    ASSERT_EQ(items[i], fixed[i]);
+  }
+}
+
+TEST(IteratorConstructorTest, FromBidirectionalIteratorRange) {
+  int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+  std::list<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput));
+  absl::FixedArray<int> const fixed(items.begin(), items.end());
+  EXPECT_THAT(fixed, testing::ElementsAreArray(kInput));
+}
+
+TEST(InitListConstructorTest, InitListConstruction) {
+  absl::FixedArray<int> fixed = {1, 2, 3};
+  EXPECT_THAT(fixed, testing::ElementsAreArray({1, 2, 3}));
+}
+
+TEST(FillConstructorTest, NonEmptyArrays) {
+  absl::FixedArray<int> stack_array(4, 1);
+  EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
+
+  absl::FixedArray<int, 0> heap_array(4, 1);
+  EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
+}
+
+TEST(FillConstructorTest, EmptyArray) {
+  absl::FixedArray<int> empty_fill(0, 1);
+  absl::FixedArray<int> empty_size(0);
+  EXPECT_EQ(empty_fill, empty_size);
+}
+
+TEST(FillConstructorTest, NotTriviallyCopyable) {
+  std::string str = "abcd";
+  absl::FixedArray<std::string> strings = {str, str, str, str};
+
+  absl::FixedArray<std::string> array(4, str);
+  EXPECT_EQ(array, strings);
+}
+
+TEST(FillConstructorTest, Disambiguation) {
+  absl::FixedArray<size_t> a(1, 2);
+  EXPECT_THAT(a, testing::ElementsAre(2));
+}
+
+TEST(FixedArrayTest, ManySizedArrays) {
+  std::vector<int> sizes;
+  for (int i = 1; i < 100; i++) sizes.push_back(i);
+  for (int i = 100; i <= 1000; i += 100) sizes.push_back(i);
+  for (int n : sizes) {
+    TestArray<0>(n);
+    TestArray<1>(n);
+    TestArray<64>(n);
+    TestArray<1000>(n);
+  }
+}
+
+TEST(FixedArrayTest, ManySizedArraysOfArraysOf1) {
+  for (int n = 1; n < 1000; n++) {
+    ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 0>(n)));
+    ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1>(n)));
+    ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 64>(n)));
+    ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1000>(n)));
+  }
+}
+
+TEST(FixedArrayTest, ManySizedArraysOfArraysOf2) {
+  for (int n = 1; n < 1000; n++) {
+    TestArrayOfArrays<2, 0>(n);
+    TestArrayOfArrays<2, 1>(n);
+    TestArrayOfArrays<2, 64>(n);
+    TestArrayOfArrays<2, 1000>(n);
+  }
+}
+
+// If value_type is put inside of a struct container,
+// we might evoke this error in a hardened build unless data() is carefully
+// written, so check on that.
+//     error: call to int __builtin___sprintf_chk(etc...)
+//     will always overflow destination buffer [-Werror]
+TEST(FixedArrayTest, AvoidParanoidDiagnostics) {
+  absl::FixedArray<char, 32> buf(32);
+  sprintf(buf.data(), "foo");  // NOLINT(runtime/printf)
+}
+
+TEST(FixedArrayTest, TooBigInlinedSpace) {
+  struct TooBig {
+    char c[1 << 20];
+  };  // too big for even one on the stack
+
+  // Simulate the data members of absl::FixedArray, a pointer and a size_t.
+  struct Data {
+    TooBig* p;
+    size_t size;
+  };
+
+  // Make sure TooBig objects are not inlined for 0 or default size.
+  static_assert(sizeof(absl::FixedArray<TooBig, 0>) == sizeof(Data),
+                "0-sized absl::FixedArray should have same size as Data.");
+  static_assert(alignof(absl::FixedArray<TooBig, 0>) == alignof(Data),
+                "0-sized absl::FixedArray should have same alignment as Data.");
+  static_assert(sizeof(absl::FixedArray<TooBig>) == sizeof(Data),
+                "default-sized absl::FixedArray should have same size as Data");
+  static_assert(
+      alignof(absl::FixedArray<TooBig>) == alignof(Data),
+      "default-sized absl::FixedArray should have same alignment as Data.");
+}
+
+// PickyDelete EXPECTs its class-scope deallocation funcs are unused.
+struct PickyDelete {
+  PickyDelete() {}
+  ~PickyDelete() {}
+  void operator delete(void* p) {
+    EXPECT_TRUE(false) << __FUNCTION__;
+    ::operator delete(p);
+  }
+  void operator delete[](void* p) {
+    EXPECT_TRUE(false) << __FUNCTION__;
+    ::operator delete[](p);
+  }
+};
+
+TEST(FixedArrayTest, UsesGlobalAlloc) { absl::FixedArray<PickyDelete, 0> a(5); }
+
+TEST(FixedArrayTest, Data) {
+  static const int kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+  absl::FixedArray<int> fa(std::begin(kInput), std::end(kInput));
+  EXPECT_EQ(fa.data(), &*fa.begin());
+  EXPECT_EQ(fa.data(), &fa[0]);
+
+  const absl::FixedArray<int>& cfa = fa;
+  EXPECT_EQ(cfa.data(), &*cfa.begin());
+  EXPECT_EQ(cfa.data(), &cfa[0]);
+}
+
+TEST(FixedArrayTest, Empty) {
+  absl::FixedArray<int> empty(0);
+  absl::FixedArray<int> inline_filled(1);
+  absl::FixedArray<int, 0> heap_filled(1);
+  EXPECT_TRUE(empty.empty());
+  EXPECT_FALSE(inline_filled.empty());
+  EXPECT_FALSE(heap_filled.empty());
+}
+
+TEST(FixedArrayTest, FrontAndBack) {
+  absl::FixedArray<int, 3 * sizeof(int)> inlined = {1, 2, 3};
+  EXPECT_EQ(inlined.front(), 1);
+  EXPECT_EQ(inlined.back(), 3);
+
+  absl::FixedArray<int, 0> allocated = {1, 2, 3};
+  EXPECT_EQ(allocated.front(), 1);
+  EXPECT_EQ(allocated.back(), 3);
+
+  absl::FixedArray<int> one_element = {1};
+  EXPECT_EQ(one_element.front(), one_element.back());
+}
+
+TEST(FixedArrayTest, ReverseIteratorInlined) {
+  absl::FixedArray<int, 5 * sizeof(int)> a = {0, 1, 2, 3, 4};
+
+  int counter = 5;
+  for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin();
+       iter != a.rend(); ++iter) {
+    counter--;
+    EXPECT_EQ(counter, *iter);
+  }
+  EXPECT_EQ(counter, 0);
+
+  counter = 5;
+  for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin();
+       iter != a.rend(); ++iter) {
+    counter--;
+    EXPECT_EQ(counter, *iter);
+  }
+  EXPECT_EQ(counter, 0);
+
+  counter = 5;
+  for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
+    counter--;
+    EXPECT_EQ(counter, *iter);
+  }
+  EXPECT_EQ(counter, 0);
+}
+
+TEST(FixedArrayTest, ReverseIteratorAllocated) {
+  absl::FixedArray<int, 0> a = {0, 1, 2, 3, 4};
+
+  int counter = 5;
+  for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin();
+       iter != a.rend(); ++iter) {
+    counter--;
+    EXPECT_EQ(counter, *iter);
+  }
+  EXPECT_EQ(counter, 0);
+
+  counter = 5;
+  for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin();
+       iter != a.rend(); ++iter) {
+    counter--;
+    EXPECT_EQ(counter, *iter);
+  }
+  EXPECT_EQ(counter, 0);
+
+  counter = 5;
+  for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
+    counter--;
+    EXPECT_EQ(counter, *iter);
+  }
+  EXPECT_EQ(counter, 0);
+}
+
+TEST(FixedArrayTest, Fill) {
+  absl::FixedArray<int, 5 * sizeof(int)> inlined(5);
+  int fill_val = 42;
+  inlined.fill(fill_val);
+  for (int i : inlined) EXPECT_EQ(i, fill_val);
+
+  absl::FixedArray<int, 0> allocated(5);
+  allocated.fill(fill_val);
+  for (int i : allocated) EXPECT_EQ(i, fill_val);
+
+  // It doesn't do anything, just make sure this compiles.
+  absl::FixedArray<int> empty(0);
+  empty.fill(fill_val);
+}
+
+#ifdef ADDRESS_SANITIZER
+TEST(FixedArrayTest, AddressSanitizerAnnotations1) {
+  absl::FixedArray<int, 32> a(10);
+  int *raw = a.data();
+  raw[0] = 0;
+  raw[9] = 0;
+  EXPECT_DEATH(raw[-2] = 0, "container-overflow");
+  EXPECT_DEATH(raw[-1] = 0, "container-overflow");
+  EXPECT_DEATH(raw[10] = 0, "container-overflow");
+  EXPECT_DEATH(raw[31] = 0, "container-overflow");
+}
+
+TEST(FixedArrayTest, AddressSanitizerAnnotations2) {
+  absl::FixedArray<char, 17> a(12);
+  char *raw = a.data();
+  raw[0] = 0;
+  raw[11] = 0;
+  EXPECT_DEATH(raw[-7] = 0, "container-overflow");
+  EXPECT_DEATH(raw[-1] = 0, "container-overflow");
+  EXPECT_DEATH(raw[12] = 0, "container-overflow");
+  EXPECT_DEATH(raw[17] = 0, "container-overflow");
+}
+
+TEST(FixedArrayTest, AddressSanitizerAnnotations3) {
+  absl::FixedArray<uint64_t, 20> a(20);
+  uint64_t *raw = a.data();
+  raw[0] = 0;
+  raw[19] = 0;
+  EXPECT_DEATH(raw[-1] = 0, "container-overflow");
+  EXPECT_DEATH(raw[20] = 0, "container-overflow");
+}
+
+TEST(FixedArrayTest, AddressSanitizerAnnotations4) {
+  absl::FixedArray<ThreeInts> a(10);
+  ThreeInts *raw = a.data();
+  raw[0] = ThreeInts();
+  raw[9] = ThreeInts();
+  // Note: raw[-1] is pointing to 12 bytes before the container range. However,
+  // there is only a 8-byte red zone before the container range, so we only
+  // access the last 4 bytes of the struct to make sure it stays within the red
+  // zone.
+  EXPECT_DEATH(raw[-1].z_ = 0, "container-overflow");
+  EXPECT_DEATH(raw[10] = ThreeInts(), "container-overflow");
+  // The actual size of storage is kDefaultBytes=256, 21*12 = 252,
+  // so reading raw[21] should still trigger the correct warning.
+  EXPECT_DEATH(raw[21] = ThreeInts(), "container-overflow");
+}
+#endif  // ADDRESS_SANITIZER
+
+}  // namespace
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
new file mode 100644
index 000000000000..f060f5c5c40f
--- /dev/null
+++ b/absl/container/inlined_vector.h
@@ -0,0 +1,1330 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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.
+//
+// -----------------------------------------------------------------------------
+// File: inlined_vector.h
+// -----------------------------------------------------------------------------
+//
+// This header file contains the declaration and definition of an "inlined
+// vector" which behaves in an equivalent fashion to a `std::vector`, except
+// that storage for small sequences of the vector are provided inline without
+// requiring any heap allocation.
+
+// An `absl::InlinedVector<T,N>` specifies the size N at which to inline as one
+// of its template parameters. Vectors of length <= N are provided inline.
+// Typically N is very small (e.g., 4) so that sequences that are expected to be
+// short do not require allocations.
+
+// An `absl::InlinedVector` does not usually require a specific allocator; if
+// the inlined vector grows beyond its initial constraints, it will need to
+// allocate (as any normal `std::vector` would) and it will generally use the
+// default allocator in that case; optionally, a custom allocator may be
+// specified using an `absl::InlinedVector<T,N,A>` construction.
+
+#ifndef ABSL_CONTAINER_INLINED_VECTOR_H_
+#define ABSL_CONTAINER_INLINED_VECTOR_H_
+
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <cstdlib>
+#include <cstring>
+#include <initializer_list>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+#include "absl/algorithm/algorithm.h"
+#include "absl/base/internal/throw_delegate.h"
+#include "absl/base/optimization.h"
+#include "absl/base/port.h"
+#include "absl/memory/memory.h"
+
+namespace absl {
+
+// -----------------------------------------------------------------------------
+// InlinedVector
+// -----------------------------------------------------------------------------
+//
+// An `absl::InlinedVector` is designed to be a drop-in replacement for
+// `std::vector` for use cases where the vector's size is sufficiently small
+// that it can be inlined. If the inlined vector does grow beyond its estimated
+// size, it will trigger an initial allocation on the heap, and will behave as a
+// `std:vector`. The API of the `absl::InlinedVector` within this file is
+// designed to cover the same API footprint as covered by `std::vector`.
+template <typename T, size_t N, typename A = std::allocator<T> >
+class InlinedVector {
+  using AllocatorTraits = std::allocator_traits<A>;
+
+ public:
+  using allocator_type = A;
+  using value_type = typename allocator_type::value_type;
+  using pointer = typename allocator_type::pointer;
+  using const_pointer = typename allocator_type::const_pointer;
+  using reference = typename allocator_type::reference;
+  using const_reference = typename allocator_type::const_reference;
+  using size_type = typename allocator_type::size_type;
+  using difference_type = typename allocator_type::difference_type;
+  using iterator = pointer;
+  using const_iterator = const_pointer;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  InlinedVector() noexcept(noexcept(allocator_type()))
+      : allocator_and_tag_(allocator_type()) {}
+
+  explicit InlinedVector(const allocator_type& alloc) noexcept
+      : allocator_and_tag_(alloc) {}
+
+  // Create a vector with n copies of value_type().
+  explicit InlinedVector(size_type n) : allocator_and_tag_(allocator_type()) {
+    InitAssign(n);
+  }
+
+  // Create a vector with n copies of elem
+  InlinedVector(size_type n, const value_type& elem,
+                const allocator_type& alloc = allocator_type())
+      : allocator_and_tag_(alloc) {
+    InitAssign(n, elem);
+  }
+
+  // Create and initialize with the elements [first .. last).
+  // The unused enable_if argument restricts this constructor so that it is
+  // elided when value_type is an integral type.  This prevents ambiguous
+  // interpretation between a call to this constructor with two integral
+  // arguments and a call to the preceding (n, elem) constructor.
+  template <typename InputIterator>
+  InlinedVector(
+      InputIterator first, InputIterator last,
+      const allocator_type& alloc = allocator_type(),
+      typename std::enable_if<!std::is_integral<InputIterator>::value>::type* =
+          nullptr)
+      : allocator_and_tag_(alloc) {
+    AppendRange(first, last);
+  }
+
+  InlinedVector(std::initializer_list<value_type> init,
+                const allocator_type& alloc = allocator_type())
+      : allocator_and_tag_(alloc) {
+    AppendRange(init.begin(), init.end());
+  }
+
+  InlinedVector(const InlinedVector& v);
+  InlinedVector(const InlinedVector& v, const allocator_type& alloc);
+
+  InlinedVector(InlinedVector&& v) noexcept(
+      absl::allocator_is_nothrow<allocator_type>::value ||
+      std::is_nothrow_move_constructible<value_type>::value);
+  InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept(
+      absl::allocator_is_nothrow<allocator_type>::value);
+
+  ~InlinedVector() { clear(); }
+
+  InlinedVector& operator=(const InlinedVector& v) {
+    // Optimized to avoid reallocation.
+    // Prefer reassignment to copy construction for elements.
+    if (size() < v.size()) {  // grow
+      reserve(v.size());
+      std::copy(v.begin(), v.begin() + size(), begin());
+      std::copy(v.begin() + size(), v.end(), std::back_inserter(*this));
+    } else {  // maybe shrink
+      erase(begin() + v.size(), end());
+      std::copy(v.begin(), v.end(), begin());
+    }
+    return *this;
+  }
+
+  InlinedVector& operator=(InlinedVector&& v) {
+    if (this == &v) {
+      return *this;
+    }
+    if (v.allocated()) {
+      clear();
+      tag().set_allocated_size(v.size());
+      init_allocation(v.allocation());
+      v.tag() = Tag();
+    } else {
+      if (allocated()) clear();
+      // Both are inlined now.
+      if (size() < v.size()) {
+        auto mid = std::make_move_iterator(v.begin() + size());
+        std::copy(std::make_move_iterator(v.begin()), mid, begin());
+        UninitializedCopy(mid, std::make_move_iterator(v.end()), end());
+      } else {
+        auto new_end = std::copy(std::make_move_iterator(v.begin()),
+                                 std::make_move_iterator(v.end()), begin());
+        Destroy(new_end, end());
+      }
+      tag().set_inline_size(v.size());
+    }
+    return *this;
+  }
+
+  InlinedVector& operator=(std::initializer_list<value_type> init) {
+    AssignRange(init.begin(), init.end());
+    return *this;
+  }
+
+  // InlinedVector::assign()
+  //
+  // Replaces the contents of the inlined vector with copies of those in the
+  // iterator range [first, last).
+  template <typename InputIterator>
+  void assign(
+      InputIterator first, InputIterator last,
+      typename std::enable_if<!std::is_integral<InputIterator>::value>::type* =
+          nullptr) {
+    AssignRange(first, last);
+  }
+
+  // Overload of `InlinedVector::assign()` to take values from elements of an
+  // initializer list
+  void assign(std::initializer_list<value_type> init) {
+    AssignRange(init.begin(), init.end());
+  }
+
+  // Overload of `InlinedVector::assign()` to replace the first `n` elements of
+  // the inlined vector with `elem` values.
+  void assign(size_type n, const value_type& elem) {
+    if (n <= size()) {  // Possibly shrink
+      std::fill_n(begin(), n, elem);
+      erase(begin() + n, end());
+      return;
+    }
+    // Grow
+    reserve(n);
+    std::fill_n(begin(), size(), elem);
+    if (allocated()) {
+      UninitializedFill(allocated_space() + size(), allocated_space() + n,
+                        elem);
+      tag().set_allocated_size(n);
+    } else {
+      UninitializedFill(inlined_space() + size(), inlined_space() + n, elem);
+      tag().set_inline_size(n);
+    }
+  }
+
+  // InlinedVector::size()
+  //
+  // Returns the number of elements in the inlined vector.
+  size_type size() const noexcept { return tag().size(); }
+
+  // InlinedVector::empty()
+  //
+  // Checks if the inlined vector has no elements.
+  bool empty() const noexcept { return (size() == 0); }
+
+  // InlinedVector::capacity()
+  //
+  // Returns the number of elements that can be stored in an inlined vector
+  // without requiring a reallocation of underlying memory. Note that for
+  // most inlined vectors, `capacity()` should equal its initial size `N`; for
+  // inlined vectors which exceed this capacity, they will no longer be inlined,
+  // and `capacity()` will equal its capacity on the allocated heap.
+  size_type capacity() const noexcept {
+    return allocated() ? allocation().capacity() : N;
+  }
+
+  // InlinedVector::max_size()
+  //
+  // Returns the maximum number of elements the vector can hold.
+  size_type max_size() const noexcept {
+    // One bit of the size storage is used to indicate whether the inlined
+    // vector is allocated; as a result, the maximum size of the container that
+    // we can express is half of the max for our size type.
+    return std::numeric_limits<size_type>::max() / 2;
+  }
+
+  // InlinedVector::data()
+  //
+  // Returns a const T* pointer to elements of the inlined vector. This pointer
+  // can be used to access (but not modify) the contained elements.
+  // Only results within the range `[0,size())` are defined.
+  const_pointer data() const noexcept {
+    return allocated() ? allocated_space() : inlined_space();
+  }
+
+  // Overload of InlinedVector::data() to return a T* pointer to elements of the
+  // inlined vector. This pointer can be used to access and modify the contained
+  // elements.
+  pointer data() noexcept {
+    return allocated() ? allocated_space() : inlined_space();
+  }
+
+  // InlinedVector::clear()
+  //
+  // Removes all elements from the inlined vector.
+  void clear() noexcept {
+    size_type s = size();
+    if (allocated()) {
+      Destroy(allocated_space(), allocated_space() + s);
+      allocation().Dealloc(allocator());
+    } else if (s != 0) {  // do nothing for empty vectors
+      Destroy(inlined_space(), inlined_space() + s);
+    }
+    tag() = Tag();
+  }
+
+  // InlinedVector::at()
+  //
+  // Returns the ith element of an inlined vector.
+  const value_type& at(size_type i) const {
+    if (ABSL_PREDICT_FALSE(i >= size())) {
+      base_internal::ThrowStdOutOfRange(
+          "InlinedVector::at failed bounds check");
+    }
+    return data()[i];
+  }
+
+  // InlinedVector::operator[]
+  //
+  // Returns the ith element of an inlined vector using the array operator.
+  const value_type& operator[](size_type i) const {
+    assert(i < size());
+    return data()[i];
+  }
+
+  // Overload of InlinedVector::at() to return the ith element of an inlined
+  // vector.
+  value_type& at(size_type i) {
+    if (i >= size()) {
+      base_internal::ThrowStdOutOfRange(
+          "InlinedVector::at failed bounds check");
+    }
+    return data()[i];
+  }
+
+  // Overload of InlinedVector::operator[] to return the ith element of an
+  // inlined vector.
+  value_type& operator[](size_type i) {
+    assert(i < size());
+    return data()[i];
+  }
+
+  // InlinedVector::back()
+  //
+  // Returns a reference to the last element of an inlined vector.
+  value_type& back() {
+    assert(!empty());
+    return at(size() - 1);
+  }
+
+  // Overload of InlinedVector::back() returns a reference to the last element
+  // of an inlined vector of const values.
+  const value_type& back() const {
+    assert(!empty());
+    return at(size() - 1);
+  }
+
+  // InlinedVector::front()
+  //
+  // Returns a reference to the first element of an inlined vector.
+  value_type& front() {
+    assert(!empty());
+    return at(0);
+  }
+
+  // Overload of InlinedVector::front() returns a reference to the first element
+  // of an inlined vector of const values.
+  const value_type& front() const {
+    assert(!empty());
+    return at(0);
+  }
+
+  // InlinedVector::emplace_back()
+  //
+  // Constructs and appends an object to the inlined vector.
+  template <typename... Args>
+  void emplace_back(Args&&... args) {
+    size_type s = size();
+    assert(s <= capacity());
+    if (ABSL_PREDICT_FALSE(s == capacity())) {
+      GrowAndEmplaceBack(std::forward<Args>(args)...);
+      return;
+    }
+    assert(s < capacity());
+
+    value_type* space;
+    if (allocated()) {
+      tag().set_allocated_size(s + 1);
+      space = allocated_space();
+    } else {
+      tag().set_inline_size(s + 1);
+      space = inlined_space();
+    }
+    Construct(space + s, std::forward<Args>(args)...);
+  }
+
+  // InlinedVector::push_back()
+  //
+  // Appends a const element to the inlined vector.
+  void push_back(const value_type& t) { emplace_back(t); }
+
+  // Overload of InlinedVector::push_back() to append a move-only element to the
+  // inlined vector.
+  void push_back(value_type&& t) { emplace_back(std::move(t)); }
+
+  // InlinedVector::pop_back()
+  //
+  // Removes the last element (which is destroyed) in the inlined vector.
+  void pop_back() {
+    assert(!empty());
+    size_type s = size();
+    if (allocated()) {
+      Destroy(allocated_space() + s - 1, allocated_space() + s);
+      tag().set_allocated_size(s - 1);
+    } else {
+      Destroy(inlined_space() + s - 1, inlined_space() + s);
+      tag().set_inline_size(s - 1);
+    }
+  }
+
+  // InlinedVector::resize()
+  //
+  // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
+  // the inlined vector's current size, extra elements are destroyed. If `n` is
+  // larger than the initial size, new elements are value-initialized.
+  void resize(size_type n);
+
+  // Overload of InlinedVector::resize() to resize the inlined vector to contain
+  // `n` elements. If `n` is larger than the current size, enough copies of
+  // `elem` are appended to increase its size to `n`.
+  void resize(size_type n, const value_type& elem);
+
+  // InlinedVector::begin()
+  //
+  // Returns an iterator to the beginning of the inlined vector.
+  iterator begin() noexcept { return data(); }
+
+  // Overload of InlinedVector::begin() for returning a const iterator to the
+  // beginning of the inlined vector.
+  const_iterator begin() const noexcept { return data(); }
+
+  // InlinedVector::cbegin()
+  //
+  // Returns a const iterator to the beginning of the inlined vector.
+  const_iterator cbegin() const noexcept { return begin(); }
+
+  // InlinedVector::end()
+  //
+  // Returns an iterator to the end of the inlined vector.
+  iterator end() noexcept { return data() + size(); }
+
+  // Overload of InlinedVector::end() for returning a const iterator to the end
+  // of the inlined vector.
+  const_iterator end() const noexcept { return data() + size(); }
+
+  // InlinedVector::cend()
+  //
+  // Returns a const iterator to the end of the inlined vector.
+  const_iterator cend() const noexcept { return end(); }
+
+  // InlinedVector::rbegin()
+  //
+  // Returns a reverse iterator from the end of the inlined vector.
+  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
+
+  // Overload of InlinedVector::rbegin() for returning a const reverse iterator
+  // from the end of the inlined vector.
+  const_reverse_iterator rbegin() const noexcept {
+    return const_reverse_iterator(end());
+  }
+
+  // InlinedVector::crbegin()
+  //
+  // Returns a const reverse iterator from the end of the inlined vector.
+  const_reverse_iterator crbegin() const noexcept { return rbegin(); }
+
+  // InlinedVector::rend()
+  //
+  // Returns a reverse iterator from the beginning of the inlined vector.
+  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
+
+  // Overload of InlinedVector::rend() for returning a const reverse iterator
+  // from the beginning of the inlined vector.
+  const_reverse_iterator rend() const noexcept {
+    return const_reverse_iterator(begin());
+  }
+
+  // InlinedVector::crend()
+  //
+  // Returns a reverse iterator from the beginning of the inlined vector.
+  const_reverse_iterator crend() const noexcept { return rend(); }
+
+  // InlinedVector::emplace()
+  //
+  // Constructs and inserts an object to the inlined vector at the given
+  // `position`, returning an iterator pointing to the newly emplaced element.
+  template <typename... Args>
+  iterator emplace(const_iterator position, Args&&... args);
+
+  // InlinedVector::insert()
+  //
+  // Inserts an element of the specified value at `position`, returning an
+  // iterator pointing to the newly inserted element.
+  iterator insert(const_iterator position, const value_type& v) {
+    return emplace(position, v);
+  }
+
+  // Overload of InlinedVector::insert() for inserting an element of the
+  // specified rvalue, returning an iterator pointing to the newly inserted
+  // element.
+  iterator insert(const_iterator position, value_type&& v) {
+    return emplace(position, std::move(v));
+  }
+
+  // Overload of InlinedVector::insert() for inserting `n` elements of the
+  // specified value at `position`, returning an iterator pointing to the first
+  // of the newly inserted elements.
+  iterator insert(const_iterator position, size_type n, const value_type& v) {
+    return InsertWithCount(position, n, v);
+  }
+
+  // Overload of `InlinedVector::insert()` to disambiguate the two
+  // three-argument overloads of `insert()`, returning an iterator pointing to
+  // the first of the newly inserted elements.
+  template <typename InputIterator,
+            typename = typename std::enable_if<std::is_convertible<
+                typename std::iterator_traits<InputIterator>::iterator_category,
+                std::input_iterator_tag>::value>::type>
+  iterator insert(const_iterator position, InputIterator first,
+                  InputIterator last) {
+    using IterType =
+        typename std::iterator_traits<InputIterator>::iterator_category;
+    return InsertWithRange(position, first, last, IterType());
+  }
+
+  // Overload of InlinedVector::insert() for inserting a list of elements at
+  // `position`, returning an iterator pointing to the first of the newly
+  // inserted elements.
+  iterator insert(const_iterator position,
+                  std::initializer_list<value_type> init) {
+    return insert(position, init.begin(), init.end());
+  }
+
+  // InlinedVector::erase()
+  //
+  // Erases the element at `position` of the inlined vector, returning an
+  // iterator pointing to the following element or the container's end if the
+  // last element was erased.
+  iterator erase(const_iterator position) {
+    assert(position >= begin());
+    assert(position < end());
+
+    iterator pos = const_cast<iterator>(position);
+    std::move(pos + 1, end(), pos);
+    pop_back();
+    return pos;
+  }
+
+  // Overload of InlinedVector::erase() for erasing all elements in the
+  // iteraror range [first, last) in the inlined vector, returning an iterator
+  // pointing to the first element following the range erased, or the
+  // container's end if range included the container's last element.
+  iterator erase(const_iterator first, const_iterator last);
+
+  // InlinedVector::reserve()
+  //
+  // Enlarges the underlying representation of the inlined vector so it can hold
+  // at least `n` elements. This method does not change `size()` or the actual
+  // contents of the vector.
+  //
+  // Note that if `n` does not exceed the inlined vector's initial size `N`,
+  // `reserve()` will have no effect; if it does exceed its initial size,
+  // `reserve()` will trigger an initial allocation and move the inlined vector
+  // onto the heap. If the vector already exists on the heap and the requested
+  // size exceeds it, a reallocation will be performed.
+  void reserve(size_type n) {
+    if (n > capacity()) {
+      // Make room for new elements
+      EnlargeBy(n - size());
+    }
+  }
+
+  // InlinedVector::swap()
+  //
+  // Swaps the contents of this inlined vector with the contents of `other`.
+  void swap(InlinedVector& other);
+
+  // InlinedVector::get_allocator()
+  //
+  // Returns the allocator of this inlined vector.
+  allocator_type get_allocator() const { return allocator(); }
+
+ private:
+  static_assert(N > 0, "inlined vector with nonpositive size");
+
+  // It holds whether the vector is allocated or not in the lowest bit.
+  // The size is held in the high bits:
+  //   size_ = (size << 1) | is_allocated;
+  class Tag {
+   public:
+    Tag() : size_(0) {}
+    size_type size() const { return size_ >> 1; }
+    void add_size(size_type n) { size_ += n << 1; }
+    void set_inline_size(size_type n) { size_ = n << 1; }
+    void set_allocated_size(size_type n) { size_ = (n << 1) | 1; }
+    bool allocated() const { return size_ & 1; }
+
+   private:
+    size_type size_;
+  };
+
+  // Derives from allocator_type to use the empty base class optimization.
+  // If the allocator_type is stateless, we can 'store'
+  // our instance of it for free.
+  class AllocatorAndTag : private allocator_type {
+   public:
+    explicit AllocatorAndTag(const allocator_type& a, Tag t = Tag())
+        : allocator_type(a), tag_(t) {
+    }
+    Tag& tag() { return tag_; }
+    const Tag& tag() const { return tag_; }
+    allocator_type& allocator() { return *this; }
+    const allocator_type& allocator() const { return *this; }
+   private:
+    Tag tag_;
+  };
+
+  class Allocation {
+   public:
+    Allocation(allocator_type& a,  // NOLINT(runtime/references)
+               size_type capacity)
+        : capacity_(capacity),
+          buffer_(AllocatorTraits::allocate(a, capacity_)) {}
+
+    void Dealloc(allocator_type& a) {  // NOLINT(runtime/references)
+      AllocatorTraits::deallocate(a, buffer(), capacity());
+    }
+
+    size_type capacity() const { return capacity_; }
+    const value_type* buffer() const { return buffer_; }
+    value_type* buffer() { return buffer_; }
+
+   private:
+    size_type capacity_;
+    value_type* buffer_;
+  };
+
+  const Tag& tag() const { return allocator_and_tag_.tag(); }
+  Tag& tag() { return allocator_and_tag_.tag(); }
+
+  Allocation& allocation() {
+    return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation);
+  }
+  const Allocation& allocation() const {
+    return reinterpret_cast<const Allocation&>(
+        rep_.allocation_storage.allocation);
+  }
+  void init_allocation(const Allocation& allocation) {
+    new (&rep_.allocation_storage.allocation) Allocation(allocation);
+  }
+
+  value_type* inlined_space() {
+    return reinterpret_cast<value_type*>(&rep_.inlined_storage.inlined);
+  }
+  const value_type* inlined_space() const {
+    return reinterpret_cast<const value_type*>(&rep_.inlined_storage.inlined);
+  }
+
+  value_type* allocated_space() {
+    return allocation().buffer();
+  }
+  const value_type* allocated_space() const {
+    return allocation().buffer();
+  }
+
+  const allocator_type& allocator() const {
+    return allocator_and_tag_.allocator();
+  }
+  allocator_type& allocator() {
+    return allocator_and_tag_.allocator();
+  }
+
+  bool allocated() const { return tag().allocated(); }
+
+  // Enlarge the underlying representation so we can store size_ + delta elems.
+  // The size is not changed, and any newly added memory is not initialized.
+  void EnlargeBy(size_type delta);
+
+  // Shift all elements from position to end() n places to the right.
+  // If the vector needs to be enlarged, memory will be allocated.
+  // Returns iterators pointing to the start of the previously-initialized
+  // portion and the start of the uninitialized portion of the created gap.
+  // The number of initialized spots is pair.second - pair.first;
+  // the number of raw spots is n - (pair.second - pair.first).
+  std::pair<iterator, iterator> ShiftRight(const_iterator position,
+                                           size_type n);
+
+  void ResetAllocation(Allocation new_allocation, size_type new_size) {
+    if (allocated()) {
+      Destroy(allocated_space(), allocated_space() + size());
+      assert(begin() == allocated_space());
+      allocation().Dealloc(allocator());
+      allocation() = new_allocation;
+    } else {
+      Destroy(inlined_space(), inlined_space() + size());
+      init_allocation(new_allocation);  // bug: only init once
+    }
+    tag().set_allocated_size(new_size);
+  }
+
+  template <typename... Args>
+  void GrowAndEmplaceBack(Args&&... args) {
+    assert(size() == capacity());
+    const size_type s = size();
+
+    Allocation new_allocation(allocator(), 2 * capacity());
+
+    Construct(new_allocation.buffer() + s, std::forward<Args>(args)...);
+    UninitializedCopy(std::make_move_iterator(data()),
+                      std::make_move_iterator(data() + s),
+                      new_allocation.buffer());
+
+    ResetAllocation(new_allocation, s + 1);
+  }
+
+  void InitAssign(size_type n);
+  void InitAssign(size_type n, const value_type& t);
+
+  template <typename... Args>
+  void Construct(pointer p, Args&&... args) {
+    AllocatorTraits::construct(allocator(), p, std::forward<Args>(args)...);
+  }
+
+  template <typename Iter>
+  void UninitializedCopy(Iter src, Iter src_last, value_type* dst) {
+    for (; src != src_last; ++dst, ++src) Construct(dst, *src);
+  }
+
+  template <typename... Args>
+  void UninitializedFill(value_type* dst, value_type* dst_last,
+                         const Args&... args) {
+    for (; dst != dst_last; ++dst) Construct(dst, args...);
+  }
+
+  // Destroy [ptr, ptr_last) in place.
+  void Destroy(value_type* ptr, value_type* ptr_last);
+
+  template <typename Iter>
+  void AppendRange(Iter first, Iter last, std::input_iterator_tag) {
+    std::copy(first, last, std::back_inserter(*this));
+  }
+
+  // Faster path for forward iterators.
+  template <typename Iter>
+  void AppendRange(Iter first, Iter last, std::forward_iterator_tag);
+
+  template <typename Iter>
+  void AppendRange(Iter first, Iter last) {
+    using IterTag = typename std::iterator_traits<Iter>::iterator_category;
+    AppendRange(first, last, IterTag());
+  }
+
+  template <typename Iter>
+  void AssignRange(Iter first, Iter last, std::input_iterator_tag);
+
+  // Faster path for forward iterators.
+  template <typename Iter>
+  void AssignRange(Iter first, Iter last, std::forward_iterator_tag);
+
+  template <typename Iter>
+  void AssignRange(Iter first, Iter last) {
+    using IterTag = typename std::iterator_traits<Iter>::iterator_category;
+    AssignRange(first, last, IterTag());
+  }
+
+  iterator InsertWithCount(const_iterator position, size_type n,
+                           const value_type& v);
+
+  template <typename InputIter>
+  iterator InsertWithRange(const_iterator position, InputIter first,
+                           InputIter last, std::input_iterator_tag);
+  template <typename ForwardIter>
+  iterator InsertWithRange(const_iterator position, ForwardIter first,
+                           ForwardIter last, std::forward_iterator_tag);
+
+  AllocatorAndTag allocator_and_tag_;
+
+  // Either the inlined or allocated representation
+  union Rep {
+    // Use struct to perform indirection that solves a bizarre compilation
+    // error on Visual Studio (all known versions).
+    struct {
+      typename std::aligned_storage<sizeof(value_type),
+                                    alignof(value_type)>::type inlined[N];
+    } inlined_storage;
+    struct {
+      typename std::aligned_storage<sizeof(Allocation),
+                                    alignof(Allocation)>::type allocation;
+    } allocation_storage;
+  } rep_;
+};
+
+// -----------------------------------------------------------------------------
+// InlinedVector Non-Member Functions
+// -----------------------------------------------------------------------------
+
+// swap()
+//
+// Swaps the contents of two inlined vectors. This convenience function
+// simply calls InlinedVector::swap(other_inlined_vector).
+template <typename T, size_t N, typename A>
+void swap(InlinedVector<T, N, A>& a,
+          InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) {
+  a.swap(b);
+}
+
+// operator==()
+//
+// Tests the equivalency of the contents of two inlined vectors.
+template <typename T, size_t N, typename A>
+bool operator==(const InlinedVector<T, N, A>& a,
+                const InlinedVector<T, N, A>& b) {
+  return absl::equal(a.begin(), a.end(), b.begin(), b.end());
+}
+
+// operator!=()
+//
+// Tests the inequality of the contents of two inlined vectors.
+template <typename T, size_t N, typename A>
+bool operator!=(const InlinedVector<T, N, A>& a,
+                const InlinedVector<T, N, A>& b) {
+  return !(a == b);
+}
+
+// operator<()
+//
+// Tests whether the contents of one inlined vector are less than the contents
+// of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator<(const InlinedVector<T, N, A>& a,
+               const InlinedVector<T, N, A>& b) {
+  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
+}
+
+// operator>()
+//
+// Tests whether the contents of one inlined vector are greater than the
+// contents of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator>(const InlinedVector<T, N, A>& a,
+               const InlinedVector<T, N, A>& b) {
+  return b < a;
+}
+
+// operator<=()
+//
+// Tests whether the contents of one inlined vector are less than or equal to
+// the contents of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator<=(const InlinedVector<T, N, A>& a,
+                const InlinedVector<T, N, A>& b) {
+  return !(b < a);
+}
+
+// operator>=()
+//
+// Tests whether the contents of one inlined vector are greater than or equal to
+// the contents of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator>=(const InlinedVector<T, N, A>& a,
+                const InlinedVector<T, N, A>& b) {
+  return !(a < b);
+}
+
+// -----------------------------------------------------------------------------
+// Implementation of InlinedVector
+// -----------------------------------------------------------------------------
+//
+// Do not depend on any implementation details below this line.
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(const InlinedVector& v)
+    : allocator_and_tag_(v.allocator()) {
+  reserve(v.size());
+  if (allocated()) {
+    UninitializedCopy(v.begin(), v.end(), allocated_space());
+    tag().set_allocated_size(v.size());
+  } else {
+    UninitializedCopy(v.begin(), v.end(), inlined_space());
+    tag().set_inline_size(v.size());
+  }
+}
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(const InlinedVector& v,
+                                      const allocator_type& alloc)
+    : allocator_and_tag_(alloc) {
+  reserve(v.size());
+  if (allocated()) {
+    UninitializedCopy(v.begin(), v.end(), allocated_space());
+    tag().set_allocated_size(v.size());
+  } else {
+    UninitializedCopy(v.begin(), v.end(), inlined_space());
+    tag().set_inline_size(v.size());
+  }
+}
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(InlinedVector&& v) noexcept(
+    absl::allocator_is_nothrow<allocator_type>::value ||
+    std::is_nothrow_move_constructible<value_type>::value)
+    : allocator_and_tag_(v.allocator_and_tag_) {
+  if (v.allocated()) {
+    // We can just steal the underlying buffer from the source.
+    // That leaves the source empty, so we clear its size.
+    init_allocation(v.allocation());
+    v.tag() = Tag();
+  } else {
+    UninitializedCopy(std::make_move_iterator(v.inlined_space()),
+                      std::make_move_iterator(v.inlined_space() + v.size()),
+                      inlined_space());
+  }
+}
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(
+    InlinedVector&& v,
+    const allocator_type&
+        alloc) noexcept(absl::allocator_is_nothrow<allocator_type>::value)
+    : allocator_and_tag_(alloc) {
+  if (v.allocated()) {
+    if (alloc == v.allocator()) {
+      // We can just steal the allocation from the source.
+      tag() = v.tag();
+      init_allocation(v.allocation());
+      v.tag() = Tag();
+    } else {
+      // We need to use our own allocator
+      reserve(v.size());
+      UninitializedCopy(std::make_move_iterator(v.begin()),
+                        std::make_move_iterator(v.end()), allocated_space());
+      tag().set_allocated_size(v.size());
+    }
+  } else {
+    UninitializedCopy(std::make_move_iterator(v.inlined_space()),
+                      std::make_move_iterator(v.inlined_space() + v.size()),
+                      inlined_space());
+    tag().set_inline_size(v.size());
+  }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::InitAssign(size_type n, const value_type& t) {
+  if (n > static_cast<size_type>(N)) {
+    Allocation new_allocation(allocator(), n);
+    init_allocation(new_allocation);
+    UninitializedFill(allocated_space(), allocated_space() + n, t);
+    tag().set_allocated_size(n);
+  } else {
+    UninitializedFill(inlined_space(), inlined_space() + n, t);
+    tag().set_inline_size(n);
+  }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::InitAssign(size_type n) {
+  if (n > static_cast<size_type>(N)) {
+    Allocation new_allocation(allocator(), n);
+    init_allocation(new_allocation);
+    UninitializedFill(allocated_space(), allocated_space() + n);
+    tag().set_allocated_size(n);
+  } else {
+    UninitializedFill(inlined_space(), inlined_space() + n);
+    tag().set_inline_size(n);
+  }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::resize(size_type n) {
+  size_type s = size();
+  if (n < s) {
+    erase(begin() + n, end());
+    return;
+  }
+  reserve(n);
+  assert(capacity() >= n);
+
+  // Fill new space with elements constructed in-place.
+  if (allocated()) {
+    UninitializedFill(allocated_space() + s, allocated_space() + n);
+    tag().set_allocated_size(n);
+  } else {
+    UninitializedFill(inlined_space() + s, inlined_space() + n);
+    tag().set_inline_size(n);
+  }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::resize(size_type n, const value_type& elem) {
+  size_type s = size();
+  if (n < s) {
+    erase(begin() + n, end());
+    return;
+  }
+  reserve(n);
+  assert(capacity() >= n);
+
+  // Fill new space with copies of 'elem'.
+  if (allocated()) {
+    UninitializedFill(allocated_space() + s, allocated_space() + n, elem);
+    tag().set_allocated_size(n);
+  } else {
+    UninitializedFill(inlined_space() + s, inlined_space() + n, elem);
+    tag().set_inline_size(n);
+  }
+}
+
+template <typename T, size_t N, typename A>
+template <typename... Args>
+typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::emplace(
+    const_iterator position, Args&&... args) {
+  assert(position >= begin());
+  assert(position <= end());
+  if (position == end()) {
+    emplace_back(std::forward<Args>(args)...);
+    return end() - 1;
+  }
+  size_type s = size();
+  size_type idx = std::distance(cbegin(), position);
+  if (s == capacity()) {
+    EnlargeBy(1);
+  }
+  assert(s < capacity());
+  iterator pos = begin() + idx;  // Set 'pos' to a post-enlarge iterator.
+
+  pointer space;
+  if (allocated()) {
+    tag().set_allocated_size(s + 1);
+    space = allocated_space();
+  } else {
+    tag().set_inline_size(s + 1);
+    space = inlined_space();
+  }
+  Construct(space + s, std::move(space[s - 1]));
+  std::move_backward(pos, space + s - 1, space + s);
+  Destroy(pos, pos + 1);
+  Construct(pos, std::forward<Args>(args)...);
+
+  return pos;
+}
+
+template <typename T, size_t N, typename A>
+typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::erase(
+    const_iterator first, const_iterator last) {
+  assert(begin() <= first);
+  assert(first <= last);
+  assert(last <= end());
+
+  iterator range_start = const_cast<iterator>(first);
+  iterator range_end = const_cast<iterator>(last);
+
+  size_type s = size();
+  ptrdiff_t erase_gap = std::distance(range_start, range_end);
+  if (erase_gap > 0) {
+    pointer space;
+    if (allocated()) {
+      space = allocated_space();
+      tag().set_allocated_size(s - erase_gap);
+    } else {
+      space = inlined_space();
+      tag().set_inline_size(s - erase_gap);
+    }
+    std::move(range_end, space + s, range_start);
+    Destroy(space + s - erase_gap, space + s);
+  }
+  return range_start;
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::swap(InlinedVector& other) {
+  using std::swap;  // Augment ADL with std::swap.
+  if (&other == this) {
+    return;
+  }
+  if (allocated() && other.allocated()) {
+    // Both out of line, so just swap the tag, allocation, and allocator.
+    swap(tag(), other.tag());
+    swap(allocation(), other.allocation());
+    swap(allocator(), other.allocator());
+    return;
+  }
+  if (!allocated() && !other.allocated()) {
+    // Both inlined: swap up to smaller size, then move remaining elements.
+    InlinedVector* a = this;
+    InlinedVector* b = &other;
+    if (size() < other.size()) {
+      swap(a, b);
+    }
+
+    const size_type a_size = a->size();
+    const size_type b_size = b->size();
+    assert(a_size >= b_size);
+    // 'a' is larger. Swap the elements up to the smaller array size.
+    std::swap_ranges(a->inlined_space(),
+                     a->inlined_space() + b_size,
+                     b->inlined_space());
+
+    // Move the remaining elements: A[b_size,a_size) -> B[b_size,a_size)
+    b->UninitializedCopy(a->inlined_space() + b_size,
+                         a->inlined_space() + a_size,
+                         b->inlined_space() + b_size);
+    a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
+
+    swap(a->tag(), b->tag());
+    swap(a->allocator(), b->allocator());
+    assert(b->size() == a_size);
+    assert(a->size() == b_size);
+    return;
+  }
+  // One is out of line, one is inline.
+  // We first move the elements from the inlined vector into the
+  // inlined space in the other vector.  We then put the other vector's
+  // pointer/capacity into the originally inlined vector and swap
+  // the tags.
+  InlinedVector* a = this;
+  InlinedVector* b = &other;
+  if (a->allocated()) {
+    swap(a, b);
+  }
+  assert(!a->allocated());
+  assert(b->allocated());
+  const size_type a_size = a->size();
+  const size_type b_size = b->size();
+  // In an optimized build, b_size would be unused.
+  (void)b_size;
+
+  // Made Local copies of size(), don't need tag() accurate anymore
+  swap(a->tag(), b->tag());
+
+  // Copy b_allocation out before b's union gets clobbered by inline_space.
+  Allocation b_allocation = b->allocation();
+
+  b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
+                       b->inlined_space());
+  a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
+
+  a->allocation() = b_allocation;
+
+  if (a->allocator() != b->allocator()) {
+    swap(a->allocator(), b->allocator());
+  }
+
+  assert(b->size() == a_size);
+  assert(a->size() == b_size);
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::EnlargeBy(size_type delta) {
+  const size_type s = size();
+  assert(s <= capacity());
+
+  size_type target = std::max(static_cast<size_type>(N), s + delta);
+
+  // Compute new capacity by repeatedly doubling current capacity
+  // TODO(psrc): Check and avoid overflow?
+  size_type new_capacity = capacity();
+  while (new_capacity < target) {
+    new_capacity <<= 1;
+  }
+
+  Allocation new_allocation(allocator(), new_capacity);
+
+  UninitializedCopy(std::make_move_iterator(data()),
+                    std::make_move_iterator(data() + s),
+                    new_allocation.buffer());
+
+  ResetAllocation(new_allocation, s);
+}
+
+template <typename T, size_t N, typename A>
+auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n)
+    -> std::pair<iterator, iterator> {
+  iterator start_used = const_cast<iterator>(position);
+  iterator start_raw = const_cast<iterator>(position);
+  size_type s = size();
+  size_type required_size = s + n;
+
+  if (required_size > capacity()) {
+    // Compute new capacity by repeatedly doubling current capacity
+    size_type new_capacity = capacity();
+    while (new_capacity < required_size) {
+      new_capacity <<= 1;
+    }
+    // Move everyone into the new allocation, leaving a gap of n for the
+    // requested shift.
+    Allocation new_allocation(allocator(), new_capacity);
+    size_type index = position - begin();
+    UninitializedCopy(std::make_move_iterator(data()),
+                      std::make_move_iterator(data() + index),
+                      new_allocation.buffer());
+    UninitializedCopy(std::make_move_iterator(data() + index),
+                      std::make_move_iterator(data() + s),
+                      new_allocation.buffer() + index + n);
+    ResetAllocation(new_allocation, s);
+
+    // New allocation means our iterator is invalid, so we'll recalculate.
+    // Since the entire gap is in new space, there's no used space to reuse.
+    start_raw = begin() + index;
+    start_used = start_raw;
+  } else {
+    // If we had enough space, it's a two-part move. Elements going into
+    // previously-unoccupied space need an UninitializedCopy. Elements
+    // going into a previously-occupied space are just a move.
+    iterator pos = const_cast<iterator>(position);
+    iterator raw_space = end();
+    size_type slots_in_used_space = raw_space - pos;
+    size_type new_elements_in_used_space = std::min(n, slots_in_used_space);
+    size_type new_elements_in_raw_space = n - new_elements_in_used_space;
+    size_type old_elements_in_used_space =
+        slots_in_used_space - new_elements_in_used_space;
+
+    UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space),
+                      std::make_move_iterator(raw_space),
+                      raw_space + new_elements_in_raw_space);
+    std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
+
+    // If the gap is entirely in raw space, the used space starts where the raw
+    // space starts, leaving no elements in used space. If the gap is entirely
+    // in used space, the raw space starts at the end of the gap, leaving all
+    // elements accounted for within the used space.
+    start_used = pos;
+    start_raw = pos + new_elements_in_used_space;
+  }
+  return std::make_pair(start_used, start_raw);
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::Destroy(value_type* ptr, value_type* ptr_last) {
+  for (value_type* p = ptr; p != ptr_last; ++p) {
+    AllocatorTraits::destroy(allocator(), p);
+  }
+
+  // Overwrite unused memory with 0xab so we can catch uninitialized usage.
+  // Cast to void* to tell the compiler that we don't care that we might be
+  // scribbling on a vtable pointer.
+#ifndef NDEBUG
+  if (ptr != ptr_last) {
+    memset(reinterpret_cast<void*>(ptr), 0xab,
+           sizeof(*ptr) * (ptr_last - ptr));
+  }
+#endif
+}
+
+template <typename T, size_t N, typename A>
+template <typename Iter>
+void InlinedVector<T, N, A>::AppendRange(Iter first, Iter last,
+                                         std::forward_iterator_tag) {
+  using Length = typename std::iterator_traits<Iter>::difference_type;
+  Length length = std::distance(first, last);
+  reserve(size() + length);
+  if (allocated()) {
+    UninitializedCopy(first, last, allocated_space() + size());
+    tag().set_allocated_size(size() + length);
+  } else {
+    UninitializedCopy(first, last, inlined_space() + size());
+    tag().set_inline_size(size() + length);
+  }
+}
+
+template <typename T, size_t N, typename A>
+template <typename Iter>
+void InlinedVector<T, N, A>::AssignRange(Iter first, Iter last,
+                                         std::input_iterator_tag) {
+  // Optimized to avoid reallocation.
+  // Prefer reassignment to copy construction for elements.
+  iterator out = begin();
+  for ( ; first != last && out != end(); ++first, ++out)
+    *out = *first;
+  erase(out, end());
+  std::copy(first, last, std::back_inserter(*this));
+}
+
+template <typename T, size_t N, typename A>
+template <typename Iter>
+void InlinedVector<T, N, A>::AssignRange(Iter first, Iter last,
+                                         std::forward_iterator_tag) {
+  using Length = typename std::iterator_traits<Iter>::difference_type;
+  Length length = std::distance(first, last);
+  // Prefer reassignment to copy construction for elements.
+  if (static_cast<size_type>(length) <= size()) {
+    erase(std::copy(first, last, begin()), end());
+    return;
+  }
+  reserve(length);
+  iterator out = begin();
+  for (; out != end(); ++first, ++out) *out = *first;
+  if (allocated()) {
+    UninitializedCopy(first, last, out);
+    tag().set_allocated_size(length);
+  } else {
+    UninitializedCopy(first, last, out);
+    tag().set_inline_size(length);
+  }
+}
+
+template <typename T, size_t N, typename A>
+auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position,
+                                             size_type n, const value_type& v)
+    -> iterator {
+  assert(position >= begin() && position <= end());
+  if (n == 0) return const_cast<iterator>(position);
+  std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+  std::fill(it_pair.first, it_pair.second, v);
+  UninitializedFill(it_pair.second, it_pair.first + n, v);
+  tag().add_size(n);
+  return it_pair.first;
+}
+
+template <typename T, size_t N, typename A>
+template <typename InputIter>
+auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
+                                             InputIter first, InputIter last,
+                                             std::input_iterator_tag)
+    -> iterator {
+  assert(position >= begin() && position <= end());
+  size_type index = position - cbegin();
+  size_type i = index;
+  while (first != last) insert(begin() + i++, *first++);
+  return begin() + index;
+}
+
+// Overload of InlinedVector::InsertWithRange()
+template <typename T, size_t N, typename A>
+template <typename ForwardIter>
+auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
+                                             ForwardIter first,
+                                             ForwardIter last,
+                                             std::forward_iterator_tag)
+    -> iterator {
+  assert(position >= begin() && position <= end());
+  if (first == last) {
+    return const_cast<iterator>(position);
+  }
+  using Length = typename std::iterator_traits<ForwardIter>::difference_type;
+  Length n = std::distance(first, last);
+  std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+  size_type used_spots = it_pair.second - it_pair.first;
+  ForwardIter open_spot = std::next(first, used_spots);
+  std::copy(first, open_spot, it_pair.first);
+  UninitializedCopy(open_spot, last, it_pair.second);
+  tag().add_size(n);
+  return it_pair.first;
+}
+
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INLINED_VECTOR_H_
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc
new file mode 100644
index 000000000000..c559a9a1fcba
--- /dev/null
+++ b/absl/container/inlined_vector_test.cc
@@ -0,0 +1,1593 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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 "absl/container/inlined_vector.h"
+
+#include <forward_list>
+#include <list>
+#include <memory>
+#include <scoped_allocator>
+#include <sstream>
+#include <stdexcept>
+#include <string>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/attributes.h"
+#include "absl/base/internal/exception_testing.h"
+#include "absl/base/internal/raw_logging.h"
+#include "absl/base/macros.h"
+#include "absl/container/internal/test_instance_tracker.h"
+#include "absl/memory/memory.h"
+#include "absl/strings/str_cat.h"
+
+namespace {
+
+using absl::test_internal::CopyableMovableInstance;
+using absl::test_internal::CopyableOnlyInstance;
+using absl::test_internal::InstanceTracker;
+using testing::AllOf;
+using testing::Each;
+using testing::ElementsAre;
+using testing::ElementsAreArray;
+using testing::Eq;
+using testing::Gt;
+using testing::PrintToString;
+
+using IntVec = absl::InlinedVector<int, 8>;
+
+MATCHER_P(SizeIs, n, "") {
+  return testing::ExplainMatchResult(n, arg.size(), result_listener);
+}
+
+MATCHER_P(CapacityIs, n, "") {
+  return testing::ExplainMatchResult(n, arg.capacity(), result_listener);
+}
+
+MATCHER_P(ValueIs, e, "") {
+  return testing::ExplainMatchResult(e, arg.value(), result_listener);
+}
+
+// TODO(bsamwel): Add support for movable-only types.
+
+// Test fixture for typed tests on BaseCountedInstance derived classes, see
+// test_instance_tracker.h.
+template <typename T>
+class InstanceTest : public ::testing::Test {};
+TYPED_TEST_CASE_P(InstanceTest);
+
+// A simple reference counted class to make sure that the proper elements are
+// destroyed in the erase(begin, end) test.
+class RefCounted {
+ public:
+  RefCounted(int value, int* count) : value_(value), count_(count) {
+    Ref();
+  }
+
+  RefCounted(const RefCounted& v)
+      : value_(v.value_), count_(v.count_) {
+    Ref();
+  }
+
+  ~RefCounted() {
+    Unref();
+    count_ = nullptr;
+  }
+
+  friend void swap(RefCounted& a, RefCounted& b) {
+    using std::swap;
+    swap(a.value_, b.value_);
+    swap(a.count_, b.count_);
+  }
+
+  RefCounted& operator=(RefCounted v) {
+    using std::swap;
+    swap(*this, v);
+    return *this;
+  }
+
+  void Ref() const {
+    ABSL_RAW_CHECK(count_ != nullptr, "");
+    ++(*count_);
+  }
+
+  void Unref() const {
+    --(*count_);
+    ABSL_RAW_CHECK(*count_ >= 0, "");
+  }
+
+  int value_;
+  int* count_;
+};
+
+using RefCountedVec = absl::InlinedVector<RefCounted, 8>;
+
+// A class with a vtable pointer
+class Dynamic {
+ public:
+  virtual ~Dynamic() {}
+};
+
+using DynamicVec = absl::InlinedVector<Dynamic, 8>;
+
+// Append 0..len-1 to *v
+template <typename Container>
+static void Fill(Container* v, int len, int offset = 0) {
+  for (int i = 0; i < len; i++) {
+    v->push_back(i + offset);
+  }
+}
+
+static IntVec Fill(int len, int offset = 0) {
+  IntVec v;
+  Fill(&v, len, offset);
+  return v;
+}
+
+// This is a stateful allocator, but the state lives outside of the
+// allocator (in whatever test is using the allocator). This is odd
+// but helps in tests where the allocator is propagated into nested
+// containers - that chain of allocators uses the same state and is
+// thus easier to query for aggregate allocation information.
+template <typename T>
+class CountingAllocator : public std::allocator<T> {
+ public:
+  using Alloc = std::allocator<T>;
+  using pointer = typename Alloc::pointer;
+  using size_type = typename Alloc::size_type;
+
+  CountingAllocator() : bytes_used_(nullptr) {}
+  explicit CountingAllocator(int64_t* b) : bytes_used_(b) {}
+
+  template <typename U>
+  CountingAllocator(const CountingAllocator<U>& x)
+      : Alloc(x), bytes_used_(x.bytes_used_) {}
+
+  pointer allocate(size_type n,
+                   std::allocator<void>::const_pointer hint = nullptr) {
+    assert(bytes_used_ != nullptr);
+    *bytes_used_ += n * sizeof(T);
+    return Alloc::allocate(n, hint);
+  }
+
+  void deallocate(pointer p, size_type n) {
+    Alloc::deallocate(p, n);
+    assert(bytes_used_ != nullptr);
+    *bytes_used_ -= n * sizeof(T);
+  }
+
+  template<typename U>
+  class rebind {
+   public:
+    using other = CountingAllocator<U>;
+  };
+
+  friend bool operator==(const CountingAllocator& a,
+                         const CountingAllocator& b) {
+    return a.bytes_used_ == b.bytes_used_;
+  }
+
+  friend bool operator!=(const CountingAllocator& a,
+                         const CountingAllocator& b) {
+    return !(a == b);
+  }
+
+  int64_t* bytes_used_;
+};
+
+TEST(IntVec, SimpleOps) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v;
+    const IntVec& cv = v;  // const alias
+
+    Fill(&v, len);
+    EXPECT_EQ(len, v.size());
+    EXPECT_LE(len, v.capacity());
+
+    for (int i = 0; i < len; i++) {
+      EXPECT_EQ(i, v[i]);
+      EXPECT_EQ(i, v.at(i));
+    }
+    EXPECT_EQ(v.begin(), v.data());
+    EXPECT_EQ(cv.begin(), cv.data());
+
+    int counter = 0;
+    for (IntVec::iterator iter = v.begin(); iter != v.end(); ++iter) {
+      EXPECT_EQ(counter, *iter);
+      counter++;
+    }
+    EXPECT_EQ(counter, len);
+
+    counter = 0;
+    for (IntVec::const_iterator iter = v.begin(); iter != v.end(); ++iter) {
+      EXPECT_EQ(counter, *iter);
+      counter++;
+    }
+    EXPECT_EQ(counter, len);
+
+    counter = 0;
+    for (IntVec::const_iterator iter = v.cbegin(); iter != v.cend(); ++iter) {
+      EXPECT_EQ(counter, *iter);
+      counter++;
+    }
+    EXPECT_EQ(counter, len);
+
+    if (len > 0) {
+      EXPECT_EQ(0, v.front());
+      EXPECT_EQ(len - 1, v.back());
+      v.pop_back();
+      EXPECT_EQ(len - 1, v.size());
+      for (int i = 0; i < v.size(); ++i) {
+        EXPECT_EQ(i, v[i]);
+        EXPECT_EQ(i, v.at(i));
+      }
+    }
+  }
+}
+
+TEST(IntVec, AtThrows) {
+  IntVec v = {1, 2, 3};
+  EXPECT_EQ(v.at(2), 3);
+  ABSL_BASE_INTERNAL_EXPECT_FAIL(v.at(3), std::out_of_range,
+                                 "failed bounds check");
+}
+
+TEST(IntVec, ReverseIterator) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v;
+    Fill(&v, len);
+
+    int counter = len;
+    for (IntVec::reverse_iterator iter = v.rbegin(); iter != v.rend(); ++iter) {
+      counter--;
+      EXPECT_EQ(counter, *iter);
+    }
+    EXPECT_EQ(counter, 0);
+
+    counter = len;
+    for (IntVec::const_reverse_iterator iter = v.rbegin(); iter != v.rend();
+         ++iter) {
+      counter--;
+      EXPECT_EQ(counter, *iter);
+    }
+    EXPECT_EQ(counter, 0);
+
+    counter = len;
+    for (IntVec::const_reverse_iterator iter = v.crbegin(); iter != v.crend();
+         ++iter) {
+      counter--;
+      EXPECT_EQ(counter, *iter);
+    }
+    EXPECT_EQ(counter, 0);
+  }
+}
+
+TEST(IntVec, Erase) {
+  for (int len = 1; len < 20; len++) {
+    for (int i = 0; i < len; ++i) {
+      IntVec v;
+      Fill(&v, len);
+      v.erase(v.begin() + i);
+      EXPECT_EQ(len - 1, v.size());
+      for (int j = 0; j < i; ++j) {
+        EXPECT_EQ(j, v[j]);
+      }
+      for (int j = i; j < len - 1; ++j) {
+        EXPECT_EQ(j + 1, v[j]);
+      }
+    }
+  }
+}
+
+// At the end of this test loop, the elements between [erase_begin, erase_end)
+// should have reference counts == 0, and all others elements should have
+// reference counts == 1.
+TEST(RefCountedVec, EraseBeginEnd) {
+  for (int len = 1; len < 20; ++len) {
+    for (int erase_begin = 0; erase_begin < len; ++erase_begin) {
+      for (int erase_end = erase_begin; erase_end <= len; ++erase_end) {
+        std::vector<int> counts(len, 0);
+        RefCountedVec v;
+        for (int i = 0; i < len; ++i) {
+          v.push_back(RefCounted(i, &counts[i]));
+        }
+
+        int erase_len = erase_end - erase_begin;
+
+        v.erase(v.begin() + erase_begin, v.begin() + erase_end);
+
+        EXPECT_EQ(len - erase_len, v.size());
+
+        // Check the elements before the first element erased.
+        for (int i = 0; i < erase_begin; ++i) {
+          EXPECT_EQ(i, v[i].value_);
+        }
+
+        // Check the elements after the first element erased.
+        for (int i = erase_begin; i < v.size(); ++i) {
+          EXPECT_EQ(i + erase_len, v[i].value_);
+        }
+
+        // Check that the elements at the beginning are preserved.
+        for (int i = 0; i < erase_begin; ++i) {
+          EXPECT_EQ(1, counts[i]);
+        }
+
+        // Check that the erased elements are destroyed
+        for (int i = erase_begin; i < erase_end; ++i) {
+          EXPECT_EQ(0, counts[i]);
+        }
+
+        // Check that the elements at the end are preserved.
+        for (int i = erase_end; i< len; ++i) {
+          EXPECT_EQ(1, counts[i]);
+        }
+      }
+    }
+  }
+}
+
+struct NoDefaultCtor {
+  explicit NoDefaultCtor(int) {}
+};
+struct NoCopy {
+  NoCopy() {}
+  NoCopy(const NoCopy&) = delete;
+};
+struct NoAssign {
+  NoAssign() {}
+  NoAssign& operator=(const NoAssign&) = delete;
+};
+struct MoveOnly {
+  MoveOnly() {}
+  MoveOnly(MoveOnly&&) = default;
+  MoveOnly& operator=(MoveOnly&&) = default;
+};
+TEST(InlinedVectorTest, NoDefaultCtor) {
+  absl::InlinedVector<NoDefaultCtor, 1> v(10, NoDefaultCtor(2));
+  (void)v;
+}
+TEST(InlinedVectorTest, NoCopy) {
+  absl::InlinedVector<NoCopy, 1> v(10);
+  (void)v;
+}
+TEST(InlinedVectorTest, NoAssign) {
+  absl::InlinedVector<NoAssign, 1> v(10);
+  (void)v;
+}
+TEST(InlinedVectorTest, MoveOnly) {
+  absl::InlinedVector<MoveOnly, 2> v;
+  v.push_back(MoveOnly{});
+  v.push_back(MoveOnly{});
+  v.push_back(MoveOnly{});
+  v.erase(v.begin());
+  v.push_back(MoveOnly{});
+  v.erase(v.begin(), v.begin() + 1);
+  v.insert(v.begin(), MoveOnly{});
+  v.emplace(v.begin());
+  v.emplace(v.begin(), MoveOnly{});
+}
+TEST(InlinedVectorTest, Noexcept) {
+  EXPECT_TRUE(std::is_nothrow_move_constructible<IntVec>::value);
+  EXPECT_TRUE((std::is_nothrow_move_constructible<
+               absl::InlinedVector<MoveOnly, 2>>::value));
+
+  struct MoveCanThrow {
+    MoveCanThrow(MoveCanThrow&&) {}
+  };
+  EXPECT_EQ(absl::default_allocator_is_nothrow::value,
+            (std::is_nothrow_move_constructible<
+                absl::InlinedVector<MoveCanThrow, 2>>::value));
+}
+
+
+TEST(IntVec, Insert) {
+  for (int len = 0; len < 20; len++) {
+    for (int pos = 0; pos <= len; pos++) {
+      {
+        // Single element
+        std::vector<int> std_v;
+        Fill(&std_v, len);
+        IntVec v;
+        Fill(&v, len);
+
+        std_v.insert(std_v.begin() + pos, 9999);
+        IntVec::iterator it = v.insert(v.cbegin() + pos, 9999);
+        EXPECT_THAT(v, ElementsAreArray(std_v));
+        EXPECT_EQ(it, v.cbegin() + pos);
+      }
+      {
+        // n elements
+        std::vector<int> std_v;
+        Fill(&std_v, len);
+        IntVec v;
+        Fill(&v, len);
+
+        IntVec::size_type n = 5;
+        std_v.insert(std_v.begin() + pos, n, 9999);
+        IntVec::iterator it = v.insert(v.cbegin() + pos, n, 9999);
+        EXPECT_THAT(v, ElementsAreArray(std_v));
+        EXPECT_EQ(it, v.cbegin() + pos);
+      }
+      {
+        // Iterator range (random access iterator)
+        std::vector<int> std_v;
+        Fill(&std_v, len);
+        IntVec v;
+        Fill(&v, len);
+
+        const std::vector<int> input = {9999, 8888, 7777};
+        std_v.insert(std_v.begin() + pos, input.cbegin(), input.cend());
+        IntVec::iterator it =
+            v.insert(v.cbegin() + pos, input.cbegin(), input.cend());
+        EXPECT_THAT(v, ElementsAreArray(std_v));
+        EXPECT_EQ(it, v.cbegin() + pos);
+      }
+      {
+        // Iterator range (forward iterator)
+        std::vector<int> std_v;
+        Fill(&std_v, len);
+        IntVec v;
+        Fill(&v, len);
+
+        const std::forward_list<int> input = {9999, 8888, 7777};
+        std_v.insert(std_v.begin() + pos, input.cbegin(), input.cend());
+        IntVec::iterator it =
+            v.insert(v.cbegin() + pos, input.cbegin(), input.cend());
+        EXPECT_THAT(v, ElementsAreArray(std_v));
+        EXPECT_EQ(it, v.cbegin() + pos);
+      }
+      {
+        // Iterator range (input iterator)
+        std::vector<int> std_v;
+        Fill(&std_v, len);
+        IntVec v;
+        Fill(&v, len);
+
+        std_v.insert(std_v.begin() + pos, {9999, 8888, 7777});
+        std::istringstream input("9999 8888 7777");
+        IntVec::iterator it =
+            v.insert(v.cbegin() + pos, std::istream_iterator<int>(input),
+                     std::istream_iterator<int>());
+        EXPECT_THAT(v, ElementsAreArray(std_v));
+        EXPECT_EQ(it, v.cbegin() + pos);
+      }
+      {
+        // Initializer list
+        std::vector<int> std_v;
+        Fill(&std_v, len);
+        IntVec v;
+        Fill(&v, len);
+
+        std_v.insert(std_v.begin() + pos, {9999, 8888});
+        IntVec::iterator it = v.insert(v.cbegin() + pos, {9999, 8888});
+        EXPECT_THAT(v, ElementsAreArray(std_v));
+        EXPECT_EQ(it, v.cbegin() + pos);
+      }
+    }
+  }
+}
+
+TEST(RefCountedVec, InsertConstructorDestructor) {
+  // Make sure the proper construction/destruction happen during insert
+  // operations.
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    for (int pos = 0; pos <= len; pos++) {
+      SCOPED_TRACE(pos);
+      std::vector<int> counts(len, 0);
+      int inserted_count = 0;
+      RefCountedVec v;
+      for (int i = 0; i < len; ++i) {
+        SCOPED_TRACE(i);
+        v.push_back(RefCounted(i, &counts[i]));
+      }
+
+      EXPECT_THAT(counts, Each(Eq(1)));
+
+      RefCounted insert_element(9999, &inserted_count);
+      EXPECT_EQ(1, inserted_count);
+      v.insert(v.begin() + pos, insert_element);
+      EXPECT_EQ(2, inserted_count);
+      // Check that the elements at the end are preserved.
+      EXPECT_THAT(counts, Each(Eq(1)));
+      EXPECT_EQ(2, inserted_count);
+    }
+  }
+}
+
+TEST(IntVec, Resize) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v;
+    Fill(&v, len);
+
+    // Try resizing up and down by k elements
+    static const int kResizeElem = 1000000;
+    for (int k = 0; k < 10; k++) {
+      // Enlarging resize
+      v.resize(len+k, kResizeElem);
+      EXPECT_EQ(len+k, v.size());
+      EXPECT_LE(len+k, v.capacity());
+      for (int i = 0; i < len+k; i++) {
+        if (i < len) {
+          EXPECT_EQ(i, v[i]);
+        } else {
+          EXPECT_EQ(kResizeElem, v[i]);
+        }
+      }
+
+      // Shrinking resize
+      v.resize(len, kResizeElem);
+      EXPECT_EQ(len, v.size());
+      EXPECT_LE(len, v.capacity());
+      for (int i = 0; i < len; i++) {
+        EXPECT_EQ(i, v[i]);
+      }
+    }
+  }
+}
+
+TEST(IntVec, InitWithLength) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v(len, 7);
+    EXPECT_EQ(len, v.size());
+    EXPECT_LE(len, v.capacity());
+    for (int i = 0; i < len; i++) {
+      EXPECT_EQ(7, v[i]);
+    }
+  }
+}
+
+TEST(IntVec, CopyConstructorAndAssignment) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v;
+    Fill(&v, len);
+    EXPECT_EQ(len, v.size());
+    EXPECT_LE(len, v.capacity());
+
+    IntVec v2(v);
+    EXPECT_TRUE(v == v2) << PrintToString(v) << PrintToString(v2);
+
+    for (int start_len = 0; start_len < 20; start_len++) {
+      IntVec v3;
+      Fill(&v3, start_len, 99);  // Add dummy elements that should go away
+      v3 = v;
+      EXPECT_TRUE(v == v3) << PrintToString(v) << PrintToString(v3);
+    }
+  }
+}
+
+TEST(IntVec, MoveConstructorAndAssignment) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v_in;
+    const int inlined_capacity = v_in.capacity();
+    Fill(&v_in, len);
+    EXPECT_EQ(len, v_in.size());
+    EXPECT_LE(len, v_in.capacity());
+
+    {
+      IntVec v_temp(v_in);
+      auto* old_data = v_temp.data();
+      IntVec v_out(std::move(v_temp));
+      EXPECT_TRUE(v_in == v_out) << PrintToString(v_in) << PrintToString(v_out);
+      if (v_in.size() > inlined_capacity) {
+        // Allocation is moved as a whole, data stays in place.
+        EXPECT_TRUE(v_out.data() == old_data);
+      } else {
+        EXPECT_FALSE(v_out.data() == old_data);
+      }
+    }
+    for (int start_len = 0; start_len < 20; start_len++) {
+      IntVec v_out;
+      Fill(&v_out, start_len, 99);  // Add dummy elements that should go away
+      IntVec v_temp(v_in);
+      auto* old_data = v_temp.data();
+      v_out = std::move(v_temp);
+      EXPECT_TRUE(v_in == v_out) << PrintToString(v_in) << PrintToString(v_out);
+      if (v_in.size() > inlined_capacity) {
+        // Allocation is moved as a whole, data stays in place.
+        EXPECT_TRUE(v_out.data() == old_data);
+      } else {
+        EXPECT_FALSE(v_out.data() == old_data);
+      }
+    }
+  }
+}
+
+TEST(OverheadTest, Storage) {
+  // Check for size overhead.
+  // In particular, ensure that std::allocator doesn't cost anything to store.
+  // The union should be absorbing some of the allocation bookkeeping overhead
+  // in the larger vectors, leaving only the size_ field as overhead.
+  EXPECT_EQ(2 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 1>) - 1 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 2>) - 2 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 3>) - 3 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 4>) - 4 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 5>) - 5 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 6>) - 6 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 7>) - 7 * sizeof(int*));
+  EXPECT_EQ(1 * sizeof(int*),
+            sizeof(absl::InlinedVector<int*, 8>) - 8 * sizeof(int*));
+}
+
+TEST(IntVec, Clear) {
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    IntVec v;
+    Fill(&v, len);
+    v.clear();
+    EXPECT_EQ(0, v.size());
+    EXPECT_EQ(v.begin(), v.end());
+  }
+}
+
+TEST(IntVec, Reserve) {
+  for (int len = 0; len < 20; len++) {
+    IntVec v;
+    Fill(&v, len);
+
+    for (int newlen = 0; newlen < 100; newlen++) {
+      const int* start_rep = v.data();
+      v.reserve(newlen);
+      const int* final_rep = v.data();
+      if (newlen <= len) {
+        EXPECT_EQ(start_rep, final_rep);
+      }
+      EXPECT_LE(newlen, v.capacity());
+
+      // Filling up to newlen should not change rep
+      while (v.size() < newlen) {
+        v.push_back(0);
+      }
+      EXPECT_EQ(final_rep, v.data());
+    }
+  }
+}
+
+TEST(StringVec, SelfRefPushBack) {
+  std::vector<std::string> std_v;
+  absl::InlinedVector<std::string, 4> v;
+  const std::string s = "A quite long std::string to ensure heap.";
+  std_v.push_back(s);
+  v.push_back(s);
+  for (int i = 0; i < 20; ++i) {
+    EXPECT_THAT(v, ElementsAreArray(std_v));
+
+    v.push_back(v.back());
+    std_v.push_back(std_v.back());
+  }
+  EXPECT_THAT(v, ElementsAreArray(std_v));
+}
+
+TEST(StringVec, SelfRefPushBackWithMove) {
+  std::vector<std::string> std_v;
+  absl::InlinedVector<std::string, 4> v;
+  const std::string s = "A quite long std::string to ensure heap.";
+  std_v.push_back(s);
+  v.push_back(s);
+  for (int i = 0; i < 20; ++i) {
+    EXPECT_EQ(v.back(), std_v.back());
+
+    v.push_back(std::move(v.back()));
+    std_v.push_back(std::move(std_v.back()));
+  }
+  EXPECT_EQ(v.back(), std_v.back());
+}
+
+TEST(StringVec, SelfMove) {
+  const std::string s = "A quite long std::string to ensure heap.";
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    absl::InlinedVector<std::string, 8> v;
+    for (int i = 0; i < len; ++i) {
+      SCOPED_TRACE(i);
+      v.push_back(s);
+    }
+    // Indirection necessary to avoid compiler warning.
+    v = std::move(*(&v));
+    // Ensure that the inlined vector is still in a valid state by copying it.
+    // We don't expect specific contents since a self-move results in an
+    // unspecified valid state.
+    std::vector<std::string> copy(v.begin(), v.end());
+  }
+}
+
+TEST(IntVec, Swap) {
+  for (int l1 = 0; l1 < 20; l1++) {
+    SCOPED_TRACE(l1);
+    for (int l2 = 0; l2 < 20; l2++) {
+      SCOPED_TRACE(l2);
+      IntVec a = Fill(l1, 0);
+      IntVec b = Fill(l2, 100);
+      {
+        using std::swap;
+        swap(a, b);
+      }
+      EXPECT_EQ(l1, b.size());
+      EXPECT_EQ(l2, a.size());
+      for (int i = 0; i < l1; i++) {
+        SCOPED_TRACE(i);
+        EXPECT_EQ(i, b[i]);
+      }
+      for (int i = 0; i < l2; i++) {
+        SCOPED_TRACE(i);
+        EXPECT_EQ(100 + i, a[i]);
+      }
+    }
+  }
+}
+
+TYPED_TEST_P(InstanceTest, Swap) {
+  using Instance = TypeParam;
+  using InstanceVec = absl::InlinedVector<Instance, 8>;
+  for (int l1 = 0; l1 < 20; l1++) {
+    SCOPED_TRACE(l1);
+    for (int l2 = 0; l2 < 20; l2++) {
+      SCOPED_TRACE(l2);
+      InstanceTracker tracker;
+      InstanceVec a, b;
+      const size_t inlined_capacity = a.capacity();
+      for (int i = 0; i < l1; i++) a.push_back(Instance(i));
+      for (int i = 0; i < l2; i++) b.push_back(Instance(100+i));
+      EXPECT_EQ(tracker.instances(), l1 + l2);
+      tracker.ResetCopiesMovesSwaps();
+      {
+        using std::swap;
+        swap(a, b);
+      }
+      EXPECT_EQ(tracker.instances(), l1 + l2);
+      if (a.size() > inlined_capacity && b.size() > inlined_capacity) {
+        EXPECT_EQ(tracker.swaps(), 0);  // Allocations are swapped.
+        EXPECT_EQ(tracker.moves(), 0);
+      } else if (a.size() <= inlined_capacity && b.size() <= inlined_capacity) {
+        EXPECT_EQ(tracker.swaps(), std::min(l1, l2));
+        // TODO(bsamwel): This should use moves when the type is movable.
+        EXPECT_EQ(tracker.copies(), std::max(l1, l2) - std::min(l1, l2));
+      } else {
+        // One is allocated and the other isn't. The allocation is transferred
+        // without copying elements, and the inlined instances are copied/moved.
+        EXPECT_EQ(tracker.swaps(), 0);
+        // TODO(bsamwel): This should use moves when the type is movable.
+        EXPECT_EQ(tracker.copies(), std::min(l1, l2));
+      }
+
+      EXPECT_EQ(l1, b.size());
+      EXPECT_EQ(l2, a.size());
+      for (int i = 0; i < l1; i++) {
+        EXPECT_EQ(i, b[i].value());
+      }
+      for (int i = 0; i < l2; i++) {
+        EXPECT_EQ(100 + i, a[i].value());
+      }
+    }
+  }
+}
+
+TEST(IntVec, EqualAndNotEqual) {
+  IntVec a, b;
+  EXPECT_TRUE(a == b);
+  EXPECT_FALSE(a != b);
+
+  a.push_back(3);
+  EXPECT_FALSE(a == b);
+  EXPECT_TRUE(a != b);
+
+  b.push_back(3);
+  EXPECT_TRUE(a == b);
+  EXPECT_FALSE(a != b);
+
+  b.push_back(7);
+  EXPECT_FALSE(a == b);
+  EXPECT_TRUE(a != b);
+
+  a.push_back(6);
+  EXPECT_FALSE(a == b);
+  EXPECT_TRUE(a != b);
+
+  a.clear();
+  b.clear();
+  for (int i = 0; i < 100; i++) {
+    a.push_back(i);
+    b.push_back(i);
+    EXPECT_TRUE(a == b);
+    EXPECT_FALSE(a != b);
+
+    b[i] = b[i] + 1;
+    EXPECT_FALSE(a == b);
+    EXPECT_TRUE(a != b);
+
+    b[i] = b[i] - 1;    // Back to before
+    EXPECT_TRUE(a == b);
+    EXPECT_FALSE(a != b);
+  }
+}
+
+TEST(IntVec, RelationalOps) {
+  IntVec a, b;
+  EXPECT_FALSE(a < b);
+  EXPECT_FALSE(b < a);
+  EXPECT_FALSE(a > b);
+  EXPECT_FALSE(b > a);
+  EXPECT_TRUE(a <= b);
+  EXPECT_TRUE(b <= a);
+  EXPECT_TRUE(a >= b);
+  EXPECT_TRUE(b >= a);
+  b.push_back(3);
+  EXPECT_TRUE(a < b);
+  EXPECT_FALSE(b < a);
+  EXPECT_FALSE(a > b);
+  EXPECT_TRUE(b > a);
+  EXPECT_TRUE(a <= b);
+  EXPECT_FALSE(b <= a);
+  EXPECT_FALSE(a >= b);
+  EXPECT_TRUE(b >= a);
+}
+
+TYPED_TEST_P(InstanceTest, CountConstructorsDestructors) {
+  using Instance = TypeParam;
+  using InstanceVec = absl::InlinedVector<Instance, 8>;
+  InstanceTracker tracker;
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    tracker.ResetCopiesMovesSwaps();
+
+    InstanceVec v;
+    const size_t inlined_capacity = v.capacity();
+    for (int i = 0; i < len; i++) {
+      v.push_back(Instance(i));
+    }
+    EXPECT_EQ(tracker.instances(), len);
+    EXPECT_GE(tracker.copies() + tracker.moves(),
+              len);  // More due to reallocation.
+    tracker.ResetCopiesMovesSwaps();
+
+    // Enlarging resize() must construct some objects
+    tracker.ResetCopiesMovesSwaps();
+    v.resize(len + 10, Instance(100));
+    EXPECT_EQ(tracker.instances(), len + 10);
+    if (len <= inlined_capacity && len + 10 > inlined_capacity) {
+      EXPECT_EQ(tracker.copies() + tracker.moves(), 10 + len);
+    } else {
+      // Only specify a minimum number of copies + moves. We don't want to
+      // depend on the reallocation policy here.
+      EXPECT_GE(tracker.copies() + tracker.moves(),
+                10);  // More due to reallocation.
+    }
+
+    // Shrinking resize() must destroy some objects
+    tracker.ResetCopiesMovesSwaps();
+    v.resize(len, Instance(100));
+    EXPECT_EQ(tracker.instances(), len);
+    EXPECT_EQ(tracker.copies(), 0);
+    EXPECT_EQ(tracker.moves(), 0);
+
+    // reserve() must not increase the number of initialized objects
+    SCOPED_TRACE("reserve");
+    v.reserve(len+1000);
+    EXPECT_EQ(tracker.instances(), len);
+    EXPECT_EQ(tracker.copies() + tracker.moves(), len);
+
+    // pop_back() and erase() must destroy one object
+    if (len > 0) {
+      tracker.ResetCopiesMovesSwaps();
+      v.pop_back();
+      EXPECT_EQ(tracker.instances(), len - 1);
+      EXPECT_EQ(tracker.copies(), 0);
+      EXPECT_EQ(tracker.moves(), 0);
+
+      if (!v.empty()) {
+        tracker.ResetCopiesMovesSwaps();
+        v.erase(v.begin());
+        EXPECT_EQ(tracker.instances(), len - 2);
+        EXPECT_EQ(tracker.copies() + tracker.moves(), len - 2);
+      }
+    }
+
+    tracker.ResetCopiesMovesSwaps();
+    int instances_before_empty_erase = tracker.instances();
+    v.erase(v.begin(), v.begin());
+    EXPECT_EQ(tracker.instances(), instances_before_empty_erase);
+    EXPECT_EQ(tracker.copies() + tracker.moves(), 0);
+  }
+}
+
+TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnCopyConstruction) {
+  using Instance = TypeParam;
+  using InstanceVec = absl::InlinedVector<Instance, 8>;
+  InstanceTracker tracker;
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    tracker.ResetCopiesMovesSwaps();
+
+    InstanceVec v;
+    for (int i = 0; i < len; i++) {
+      v.push_back(Instance(i));
+    }
+    EXPECT_EQ(tracker.instances(), len);
+    EXPECT_GE(tracker.copies() + tracker.moves(),
+              len);  // More due to reallocation.
+    tracker.ResetCopiesMovesSwaps();
+    {  // Copy constructor should create 'len' more instances.
+      InstanceVec v_copy(v);
+      EXPECT_EQ(tracker.instances(), len + len);
+      EXPECT_EQ(tracker.copies(), len);
+      EXPECT_EQ(tracker.moves(), 0);
+    }
+    EXPECT_EQ(tracker.instances(), len);
+  }
+}
+
+TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnMoveConstruction) {
+  using Instance = TypeParam;
+  using InstanceVec = absl::InlinedVector<Instance, 8>;
+  InstanceTracker tracker;
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    tracker.ResetCopiesMovesSwaps();
+
+    InstanceVec v;
+    const size_t inlined_capacity = v.capacity();
+    for (int i = 0; i < len; i++) {
+      v.push_back(Instance(i));
+    }
+    EXPECT_EQ(tracker.instances(), len);
+    EXPECT_GE(tracker.copies() + tracker.moves(),
+              len);  // More due to reallocation.
+    tracker.ResetCopiesMovesSwaps();
+    {
+      InstanceVec v_copy(std::move(v));
+      if (len > inlined_capacity) {
+        // Allocation is moved as a whole.
+        EXPECT_EQ(tracker.instances(), len);
+        EXPECT_EQ(tracker.live_instances(), len);
+        // Tests an implementation detail, don't rely on this in your code.
+        EXPECT_EQ(v.size(), 0);  // NOLINT misc-use-after-move
+        EXPECT_EQ(tracker.copies(), 0);
+        EXPECT_EQ(tracker.moves(), 0);
+      } else {
+        EXPECT_EQ(tracker.instances(), len + len);
+        if (Instance::supports_move()) {
+          EXPECT_EQ(tracker.live_instances(), len);
+          EXPECT_EQ(tracker.copies(), 0);
+          EXPECT_EQ(tracker.moves(), len);
+        } else {
+          EXPECT_EQ(tracker.live_instances(), len + len);
+          EXPECT_EQ(tracker.copies(), len);
+          EXPECT_EQ(tracker.moves(), 0);
+        }
+      }
+      EXPECT_EQ(tracker.swaps(), 0);
+    }
+  }
+}
+
+TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnAssignment) {
+  using Instance = TypeParam;
+  using InstanceVec = absl::InlinedVector<Instance, 8>;
+  InstanceTracker tracker;
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    for (int longorshort = 0; longorshort <= 1; ++longorshort) {
+      SCOPED_TRACE(longorshort);
+      tracker.ResetCopiesMovesSwaps();
+
+      InstanceVec longer, shorter;
+      for (int i = 0; i < len; i++) {
+        longer.push_back(Instance(i));
+        shorter.push_back(Instance(i));
+      }
+      longer.push_back(Instance(len));
+      EXPECT_EQ(tracker.instances(), len + len + 1);
+      EXPECT_GE(tracker.copies() + tracker.moves(),
+                len + len + 1);  // More due to reallocation.
+
+      tracker.ResetCopiesMovesSwaps();
+      if (longorshort) {
+        shorter = longer;
+        EXPECT_EQ(tracker.instances(), (len + 1) + (len + 1));
+        EXPECT_GE(tracker.copies() + tracker.moves(),
+                  len + 1);  // More due to reallocation.
+      } else {
+        longer = shorter;
+        EXPECT_EQ(tracker.instances(), len + len);
+        EXPECT_EQ(tracker.copies() + tracker.moves(), len);
+      }
+    }
+  }
+}
+
+TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnMoveAssignment) {
+  using Instance = TypeParam;
+  using InstanceVec = absl::InlinedVector<Instance, 8>;
+  InstanceTracker tracker;
+  for (int len = 0; len < 20; len++) {
+    SCOPED_TRACE(len);
+    for (int longorshort = 0; longorshort <= 1; ++longorshort) {
+      SCOPED_TRACE(longorshort);
+      tracker.ResetCopiesMovesSwaps();
+
+      InstanceVec longer, shorter;
+      const int inlined_capacity = longer.capacity();
+      for (int i = 0; i < len; i++) {
+        longer.push_back(Instance(i));
+        shorter.push_back(Instance(i));
+      }
+      longer.push_back(Instance(len));
+      EXPECT_EQ(tracker.instances(), len + len + 1);
+      EXPECT_GE(tracker.copies() + tracker.moves(),
+                len + len + 1);  // More due to reallocation.
+
+      tracker.ResetCopiesMovesSwaps();
+      int src_len;
+      if (longorshort) {
+        src_len = len + 1;
+        shorter = std::move(longer);
+      } else {
+        src_len = len;
+        longer = std::move(shorter);
+      }
+      if (src_len > inlined_capacity) {
+        // Allocation moved as a whole.
+        EXPECT_EQ(tracker.instances(), src_len);
+        EXPECT_EQ(tracker.live_instances(), src_len);
+        EXPECT_EQ(tracker.copies(), 0);
+        EXPECT_EQ(tracker.moves(), 0);
+      } else {
+        // Elements are all copied.
+        EXPECT_EQ(tracker.instances(), src_len + src_len);
+        if (Instance::supports_move()) {
+          EXPECT_EQ(tracker.copies(), 0);
+          EXPECT_EQ(tracker.moves(), src_len);
+          EXPECT_EQ(tracker.live_instances(), src_len);
+        } else {
+          EXPECT_EQ(tracker.copies(), src_len);
+          EXPECT_EQ(tracker.moves(), 0);
+          EXPECT_EQ(tracker.live_instances(), src_len + src_len);
+        }
+      }
+      EXPECT_EQ(tracker.swaps(), 0);
+    }
+  }
+}
+
+TEST(CountElemAssign, SimpleTypeWithInlineBacking) {
+  for (size_t original_size = 0; original_size <= 5; ++original_size) {
+    SCOPED_TRACE(original_size);
+    // Original contents are [12345, 12345, ...]
+    std::vector<int> original_contents(original_size, 12345);
+
+    absl::InlinedVector<int, 2> v(original_contents.begin(),
+                                  original_contents.end());
+    v.assign(2, 123);
+    EXPECT_THAT(v, AllOf(SizeIs(2), ElementsAre(123, 123)));
+    if (original_size <= 2) {
+      // If the original had inline backing, it should stay inline.
+      EXPECT_EQ(2, v.capacity());
+    }
+  }
+}
+
+TEST(CountElemAssign, SimpleTypeWithAllocation) {
+  for (size_t original_size = 0; original_size <= 5; ++original_size) {
+    SCOPED_TRACE(original_size);
+    // Original contents are [12345, 12345, ...]
+    std::vector<int> original_contents(original_size, 12345);
+
+    absl::InlinedVector<int, 2> v(original_contents.begin(),
+                                  original_contents.end());
+    v.assign(3, 123);
+    EXPECT_THAT(v, AllOf(SizeIs(3), ElementsAre(123, 123, 123)));
+    EXPECT_LE(v.size(), v.capacity());
+  }
+}
+
+TYPED_TEST_P(InstanceTest, CountElemAssignInlineBacking) {
+  using Instance = TypeParam;
+  for (size_t original_size = 0; original_size <= 5; ++original_size) {
+    SCOPED_TRACE(original_size);
+    // Original contents are [12345, 12345, ...]
+    std::vector<Instance> original_contents(original_size, Instance(12345));
+
+    absl::InlinedVector<Instance, 2> v(original_contents.begin(),
+                                       original_contents.end());
+    v.assign(2, Instance(123));
+    EXPECT_THAT(v, AllOf(SizeIs(2), ElementsAre(ValueIs(123), ValueIs(123))));
+    if (original_size <= 2) {
+      // If the original had inline backing, it should stay inline.
+      EXPECT_EQ(2, v.capacity());
+    }
+  }
+}
+
+template <typename Instance>
+void InstanceCountElemAssignWithAllocationTest() {
+  for (size_t original_size = 0; original_size <= 5; ++original_size) {
+    SCOPED_TRACE(original_size);
+    // Original contents are [12345, 12345, ...]
+    std::vector<Instance> original_contents(original_size, Instance(12345));
+
+    absl::InlinedVector<Instance, 2> v(original_contents.begin(),
+                                       original_contents.end());
+    v.assign(3, Instance(123));
+    EXPECT_THAT(v,
+                AllOf(SizeIs(3),
+                      ElementsAre(ValueIs(123), ValueIs(123), ValueIs(123))));
+    EXPECT_LE(v.size(), v.capacity());
+  }
+}
+TEST(CountElemAssign, WithAllocationCopyableInstance) {
+  InstanceCountElemAssignWithAllocationTest<CopyableOnlyInstance>();
+}
+TEST(CountElemAssign, WithAllocationCopyableMovableInstance) {
+  InstanceCountElemAssignWithAllocationTest<CopyableMovableInstance>();
+}
+
+TEST(RangedConstructor, SimpleType) {
+  std::vector<int> source_v = {4, 5, 6};
+  // First try to fit in inline backing
+  absl::InlinedVector<int, 4> v(source_v.begin(), source_v.end());
+  EXPECT_EQ(3, v.size());
+  EXPECT_EQ(4, v.capacity());  // Indication that we're still on inlined storage
+  EXPECT_EQ(4, v[0]);
+  EXPECT_EQ(5, v[1]);
+  EXPECT_EQ(6, v[2]);
+
+  // Now, force a re-allocate
+  absl::InlinedVector<int, 2> realloc_v(source_v.begin(), source_v.end());
+  EXPECT_EQ(3, realloc_v.size());
+  EXPECT_LT(2, realloc_v.capacity());
+  EXPECT_EQ(4, realloc_v[0]);
+  EXPECT_EQ(5, realloc_v[1]);
+  EXPECT_EQ(6, realloc_v[2]);
+}
+
+// Test for ranged constructors using Instance as the element type and
+// SourceContainer as the source container type.
+template <typename Instance, typename SourceContainer, int inlined_capacity>
+void InstanceRangedConstructorTestForContainer() {
+  InstanceTracker tracker;
+  SourceContainer source_v = {Instance(0), Instance(1)};
+  tracker.ResetCopiesMovesSwaps();
+  absl::InlinedVector<Instance, inlined_capacity> v(source_v.begin(),
+                                                    source_v.end());
+  EXPECT_EQ(2, v.size());
+  EXPECT_LT(1, v.capacity());
+  EXPECT_EQ(0, v[0].value());
+  EXPECT_EQ(1, v[1].value());
+  EXPECT_EQ(tracker.copies(), 2);
+  EXPECT_EQ(tracker.moves(), 0);
+}
+
+template <typename Instance, int inlined_capacity>
+void InstanceRangedConstructorTestWithCapacity() {
+  // Test with const and non-const, random access and non-random-access sources.
+  // TODO(bsamwel): Test with an input iterator source.
+  {
+    SCOPED_TRACE("std::list");
+    InstanceRangedConstructorTestForContainer<Instance, std::list<Instance>,
+                                              inlined_capacity>();
+    {
+      SCOPED_TRACE("const std::list");
+      InstanceRangedConstructorTestForContainer<
+          Instance, const std::list<Instance>, inlined_capacity>();
+    }
+    {
+      SCOPED_TRACE("std::vector");
+      InstanceRangedConstructorTestForContainer<Instance, std::vector<Instance>,
+                                                inlined_capacity>();
+    }
+    {
+      SCOPED_TRACE("const std::vector");
+      InstanceRangedConstructorTestForContainer<
+          Instance, const std::vector<Instance>, inlined_capacity>();
+    }
+  }
+}
+
+TYPED_TEST_P(InstanceTest, RangedConstructor) {
+  using Instance = TypeParam;
+  SCOPED_TRACE("capacity=1");
+  InstanceRangedConstructorTestWithCapacity<Instance, 1>();
+  SCOPED_TRACE("capacity=2");
+  InstanceRangedConstructorTestWithCapacity<Instance, 2>();
+}
+
+TEST(RangedConstructor, ElementsAreConstructed) {
+  std::vector<std::string> source_v = {"cat", "dog"};
+
+  // Force expansion and re-allocation of v.  Ensures that when the vector is
+  // expanded that new elements are constructed.
+  absl::InlinedVector<std::string, 1> v(source_v.begin(), source_v.end());
+  EXPECT_EQ("cat", v[0]);
+  EXPECT_EQ("dog", v[1]);
+}
+
+TEST(RangedAssign, SimpleType) {
+  // Test for all combinations of original sizes (empty and non-empty inline,
+  // and out of line) and target sizes.
+  for (size_t original_size = 0; original_size <= 5; ++original_size) {
+    SCOPED_TRACE(original_size);
+    // Original contents are [12345, 12345, ...]
+    std::vector<int> original_contents(original_size, 12345);
+
+    for (size_t target_size = 0; target_size <= 5; ++target_size) {
+      SCOPED_TRACE(target_size);
+
+      // New contents are [3, 4, ...]
+      std::vector<int> new_contents;
+      for (size_t i = 0; i < target_size; ++i) {
+        new_contents.push_back(i + 3);
+      }
+
+      absl::InlinedVector<int, 3> v(original_contents.begin(),
+                                    original_contents.end());
+      v.assign(new_contents.begin(), new_contents.end());
+
+      EXPECT_EQ(new_contents.size(), v.size());
+      EXPECT_LE(new_contents.size(), v.capacity());
+      if (target_size <= 3 && original_size <= 3) {
+        // Storage should stay inline when target size is small.
+        EXPECT_EQ(3, v.capacity());
+      }
+      EXPECT_THAT(v, ElementsAreArray(new_contents));
+    }
+  }
+}
+
+// Returns true if lhs and rhs have the same value.
+template <typename Instance>
+static bool InstanceValuesEqual(const Instance& lhs, const Instance& rhs) {
+  return lhs.value() == rhs.value();
+}
+
+// Test for ranged assign() using Instance as the element type and
+// SourceContainer as the source container type.
+template <typename Instance, typename SourceContainer>
+void InstanceRangedAssignTestForContainer() {
+  // Test for all combinations of original sizes (empty and non-empty inline,
+  // and out of line) and target sizes.
+  for (size_t original_size = 0; original_size <= 5; ++original_size) {
+    SCOPED_TRACE(original_size);
+    // Original contents are [12345, 12345, ...]
+    std::vector<Instance> original_contents(original_size, Instance(12345));
+
+    for (size_t target_size = 0; target_size <= 5; ++target_size) {
+      SCOPED_TRACE(target_size);
+
+      // New contents are [3, 4, ...]
+      // Generate data using a non-const container, because SourceContainer
+      // itself may be const.
+      // TODO(bsamwel): Test with an input iterator.
+      std::vector<Instance> new_contents_in;
+      for (size_t i = 0; i < target_size; ++i) {
+        new_contents_in.push_back(Instance(i + 3));
+      }
+      SourceContainer new_contents(new_contents_in.begin(),
+                                   new_contents_in.end());
+
+      absl::InlinedVector<Instance, 3> v(original_contents.begin(),
+                                         original_contents.end());
+      v.assign(new_contents.begin(), new_contents.end());
+
+      EXPECT_EQ(new_contents.size(), v.size());
+      EXPECT_LE(new_contents.size(), v.capacity());
+      if (target_size <= 3 && original_size <= 3) {
+        // Storage should stay inline when target size is small.
+        EXPECT_EQ(3, v.capacity());
+      }
+      EXPECT_TRUE(std::equal(v.begin(), v.end(), new_contents.begin(),
+                             InstanceValuesEqual<Instance>));
+    }
+  }
+}
+
+TYPED_TEST_P(InstanceTest, RangedAssign) {
+  using Instance = TypeParam;
+  // Test with const and non-const, random access and non-random-access sources.
+  // TODO(bsamwel): Test with an input iterator source.
+  SCOPED_TRACE("std::list");
+  InstanceRangedAssignTestForContainer<Instance, std::list<Instance>>();
+  SCOPED_TRACE("const std::list");
+  InstanceRangedAssignTestForContainer<Instance, const std::list<Instance>>();
+  SCOPED_TRACE("std::vector");
+  InstanceRangedAssignTestForContainer<Instance, std::vector<Instance>>();
+  SCOPED_TRACE("const std::vector");
+  InstanceRangedAssignTestForContainer<Instance, const std::vector<Instance>>();
+}
+
+TEST(InitializerListConstructor, SimpleTypeWithInlineBacking) {
+  EXPECT_THAT((absl::InlinedVector<int, 4>{4, 5, 6}),
+              AllOf(SizeIs(3), CapacityIs(4), ElementsAre(4, 5, 6)));
+}
+
+TEST(InitializerListConstructor, SimpleTypeWithReallocationRequired) {
+  EXPECT_THAT((absl::InlinedVector<int, 2>{4, 5, 6}),
+              AllOf(SizeIs(3), CapacityIs(Gt(2)), ElementsAre(4, 5, 6)));
+}
+
+TEST(InitializerListConstructor, DisparateTypesInList) {
+  EXPECT_THAT((absl::InlinedVector<int, 2>{-7, 8ULL}), ElementsAre(-7, 8));
+
+  EXPECT_THAT((absl::InlinedVector<std::string, 2>{"foo", std::string("bar")}),
+              ElementsAre("foo", "bar"));
+}
+
+TEST(InitializerListConstructor, ComplexTypeWithInlineBacking) {
+  EXPECT_THAT((absl::InlinedVector<CopyableMovableInstance, 1>{
+                  CopyableMovableInstance(0)}),
+              AllOf(SizeIs(1), CapacityIs(1), ElementsAre(ValueIs(0))));
+}
+
+TEST(InitializerListConstructor, ComplexTypeWithReallocationRequired) {
+  EXPECT_THAT(
+      (absl::InlinedVector<CopyableMovableInstance, 1>{
+          CopyableMovableInstance(0), CopyableMovableInstance(1)}),
+      AllOf(SizeIs(2), CapacityIs(Gt(1)), ElementsAre(ValueIs(0), ValueIs(1))));
+}
+
+TEST(InitializerListAssign, SimpleTypeFitsInlineBacking) {
+  for (size_t original_size = 0; original_size <= 4; ++original_size) {
+    SCOPED_TRACE(original_size);
+
+    absl::InlinedVector<int, 2> v1(original_size, 12345);
+    const size_t original_capacity_v1 = v1.capacity();
+    v1.assign({3});
+    EXPECT_THAT(
+        v1, AllOf(SizeIs(1), CapacityIs(original_capacity_v1), ElementsAre(3)));
+
+    absl::InlinedVector<int, 2> v2(original_size, 12345);
+    const size_t original_capacity_v2 = v2.capacity();
+    v2 = {3};
+    EXPECT_THAT(
+        v2, AllOf(SizeIs(1), CapacityIs(original_capacity_v2), ElementsAre(3)));
+  }
+}
+
+TEST(InitializerListAssign, SimpleTypeDoesNotFitInlineBacking) {
+  for (size_t original_size = 0; original_size <= 4; ++original_size) {
+    SCOPED_TRACE(original_size);
+    absl::InlinedVector<int, 2> v1(original_size, 12345);
+    v1.assign({3, 4, 5});
+    EXPECT_THAT(v1, AllOf(SizeIs(3), ElementsAre(3, 4, 5)));
+    EXPECT_LE(3, v1.capacity());
+
+    absl::InlinedVector<int, 2> v2(original_size, 12345);
+    v2 = {3, 4, 5};
+    EXPECT_THAT(v2, AllOf(SizeIs(3), ElementsAre(3, 4, 5)));
+    EXPECT_LE(3, v2.capacity());
+  }
+}
+
+TEST(InitializerListAssign, DisparateTypesInList) {
+  absl::InlinedVector<int, 2> v_int1;
+  v_int1.assign({-7, 8ULL});
+  EXPECT_THAT(v_int1, ElementsAre(-7, 8));
+
+  absl::InlinedVector<int, 2> v_int2;
+  v_int2 = {-7, 8ULL};
+  EXPECT_THAT(v_int2, ElementsAre(-7, 8));
+
+  absl::InlinedVector<std::string, 2> v_string1;
+  v_string1.assign({"foo", std::string("bar")});
+  EXPECT_THAT(v_string1, ElementsAre("foo", "bar"));
+
+  absl::InlinedVector<std::string, 2> v_string2;
+  v_string2 = {"foo", std::string("bar")};
+  EXPECT_THAT(v_string2, ElementsAre("foo", "bar"));
+}
+
+TYPED_TEST_P(InstanceTest, InitializerListAssign) {
+  using Instance = TypeParam;
+  for (size_t original_size = 0; original_size <= 4; ++original_size) {
+    SCOPED_TRACE(original_size);
+    absl::InlinedVector<Instance, 2> v(original_size, Instance(12345));
+    const size_t original_capacity = v.capacity();
+    v.assign({Instance(3)});
+    EXPECT_THAT(v, AllOf(SizeIs(1), CapacityIs(original_capacity),
+                         ElementsAre(ValueIs(3))));
+  }
+  for (size_t original_size = 0; original_size <= 4; ++original_size) {
+    SCOPED_TRACE(original_size);
+    absl::InlinedVector<Instance, 2> v(original_size, Instance(12345));
+    v.assign({Instance(3), Instance(4), Instance(5)});
+    EXPECT_THAT(v, AllOf(SizeIs(3),
+                         ElementsAre(ValueIs(3), ValueIs(4), ValueIs(5))));
+    EXPECT_LE(3, v.capacity());
+  }
+}
+
+REGISTER_TYPED_TEST_CASE_P(InstanceTest, Swap, CountConstructorsDestructors,
+                           CountConstructorsDestructorsOnCopyConstruction,
+                           CountConstructorsDestructorsOnMoveConstruction,
+                           CountConstructorsDestructorsOnAssignment,
+                           CountConstructorsDestructorsOnMoveAssignment,
+                           CountElemAssignInlineBacking, RangedConstructor,
+                           RangedAssign, InitializerListAssign);
+
+using InstanceTypes =
+    ::testing::Types<CopyableOnlyInstance, CopyableMovableInstance>;
+INSTANTIATE_TYPED_TEST_CASE_P(InstanceTestOnTypes, InstanceTest, InstanceTypes);
+
+TEST(DynamicVec, DynamicVecCompiles) {
+  DynamicVec v;
+  (void)v;
+}
+
+TEST(AllocatorSupportTest, Constructors) {
+  using MyAlloc = CountingAllocator<int>;
+  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
+  const int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
+  int64_t allocated = 0;
+  MyAlloc alloc(&allocated);
+  { AllocVec ABSL_ATTRIBUTE_UNUSED v; }
+  { AllocVec ABSL_ATTRIBUTE_UNUSED v(alloc); }
+  { AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc); }
+  { AllocVec ABSL_ATTRIBUTE_UNUSED v({1, 2, 3}, alloc); }
+
+  AllocVec v2;
+  { AllocVec ABSL_ATTRIBUTE_UNUSED v(v2, alloc); }
+  { AllocVec ABSL_ATTRIBUTE_UNUSED v(std::move(v2), alloc); }
+}
+
+TEST(AllocatorSupportTest, CountAllocations) {
+  using MyAlloc = CountingAllocator<int>;
+  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
+  const int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
+  int64_t allocated = 0;
+  MyAlloc alloc(&allocated);
+  {
+    AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + 4, alloc);
+    EXPECT_THAT(allocated, 0);
+  }
+  EXPECT_THAT(allocated, 0);
+  {
+    AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc);
+    EXPECT_THAT(allocated, v.size() * sizeof(int));
+  }
+  EXPECT_THAT(allocated, 0);
+  {
+    AllocVec v(4, 1, alloc);
+    EXPECT_THAT(allocated, 0);
+
+    int64_t allocated2 = 0;
+    MyAlloc alloc2(&allocated2);
+    AllocVec v2(v, alloc2);
+    EXPECT_THAT(allocated2, 0);
+
+    int64_t allocated3 = 0;
+    MyAlloc alloc3(&allocated3);
+    AllocVec v3(std::move(v), alloc3);
+    EXPECT_THAT(allocated3, 0);
+  }
+  EXPECT_THAT(allocated, 0);
+  {
+    AllocVec v(8, 2, alloc);
+    EXPECT_THAT(allocated, v.size() * sizeof(int));
+
+    int64_t allocated2 = 0;
+    MyAlloc alloc2(&allocated2);
+    AllocVec v2(v, alloc2);
+    EXPECT_THAT(allocated2, v2.size() * sizeof(int));
+
+    int64_t allocated3 = 0;
+    MyAlloc alloc3(&allocated3);
+    AllocVec v3(std::move(v), alloc3);
+    EXPECT_THAT(allocated3, v3.size() * sizeof(int));
+  }
+}
+
+TEST(AllocatorSupportTest, SwapBothAllocated) {
+  using MyAlloc = CountingAllocator<int>;
+  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
+  int64_t allocated1 = 0;
+  int64_t allocated2 = 0;
+  {
+    const int ia1[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
+    const int ia2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+    MyAlloc a1(&allocated1);
+    MyAlloc a2(&allocated2);
+    AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1);
+    AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2);
+    EXPECT_LT(v1.capacity(), v2.capacity());
+    EXPECT_THAT(allocated1, v1.capacity() * sizeof(int));
+    EXPECT_THAT(allocated2, v2.capacity() * sizeof(int));
+    v1.swap(v2);
+    EXPECT_THAT(v1, ElementsAreArray(ia2));
+    EXPECT_THAT(v2, ElementsAreArray(ia1));
+    EXPECT_THAT(allocated1, v2.capacity() * sizeof(int));
+    EXPECT_THAT(allocated2, v1.capacity() * sizeof(int));
+  }
+  EXPECT_THAT(allocated1, 0);
+  EXPECT_THAT(allocated2, 0);
+}
+
+TEST(AllocatorSupportTest, SwapOneAllocated) {
+  using MyAlloc = CountingAllocator<int>;
+  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
+  int64_t allocated1 = 0;
+  int64_t allocated2 = 0;
+  {
+    const int ia1[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
+    const int ia2[] = { 0, 1, 2, 3 };
+    MyAlloc a1(&allocated1);
+    MyAlloc a2(&allocated2);
+    AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1);
+    AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2);
+    EXPECT_THAT(allocated1, v1.capacity() * sizeof(int));
+    EXPECT_THAT(allocated2, 0);
+    v1.swap(v2);
+    EXPECT_THAT(v1, ElementsAreArray(ia2));
+    EXPECT_THAT(v2, ElementsAreArray(ia1));
+    EXPECT_THAT(allocated1, v2.capacity() * sizeof(int));
+    EXPECT_THAT(allocated2, 0);
+    EXPECT_TRUE(v2.get_allocator() == a1);
+    EXPECT_TRUE(v1.get_allocator() == a2);
+  }
+  EXPECT_THAT(allocated1, 0);
+  EXPECT_THAT(allocated2, 0);
+}
+
+TEST(AllocatorSupportTest, ScopedAllocatorWorks) {
+  using StdVector = std::vector<int, CountingAllocator<int>>;
+  using MyAlloc =
+      std::scoped_allocator_adaptor<CountingAllocator<StdVector>>;
+  using AllocVec = absl::InlinedVector<StdVector, 4, MyAlloc>;
+
+  int64_t allocated = 0;
+  AllocVec vec(MyAlloc{CountingAllocator<StdVector>{&allocated}});
+  EXPECT_EQ(allocated, 0);
+
+  // This default constructs a vector<int>, but the allocator should pass itself
+  // into the vector<int>.
+  // The absl::InlinedVector does not allocate any memory.
+  // The vector<int> does not allocate any memory.
+  vec.resize(1);
+  EXPECT_EQ(allocated, 0);
+
+  // We make vector<int> allocate memory.
+  // It must go through the allocator even though we didn't construct the
+  // vector directly.
+  vec[0].push_back(1);
+  EXPECT_EQ(allocated, sizeof(int) * 1);
+
+  // Another allocating vector.
+  vec.push_back(vec[0]);
+  EXPECT_EQ(allocated, sizeof(int) * 2);
+
+  // Overflow the inlined memory.
+  // The absl::InlinedVector will now allocate.
+  vec.resize(5);
+  EXPECT_EQ(allocated, sizeof(int) * 2 + sizeof(StdVector) * 8);
+
+  // Adding one more in external mode should also work.
+  vec.push_back(vec[0]);
+  EXPECT_EQ(allocated, sizeof(int) * 3 + sizeof(StdVector) * 8);
+
+  // And extending these should still work.
+  vec[0].push_back(1);
+  EXPECT_EQ(allocated, sizeof(int) * 4 + sizeof(StdVector) * 8);
+
+  vec.clear();
+  EXPECT_EQ(allocated, 0);
+}
+
+}  // anonymous namespace
diff --git a/absl/container/internal/test_instance_tracker.cc b/absl/container/internal/test_instance_tracker.cc
new file mode 100644
index 000000000000..fe00aca8fb98
--- /dev/null
+++ b/absl/container/internal/test_instance_tracker.cc
@@ -0,0 +1,26 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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 "absl/container/internal/test_instance_tracker.h"
+
+namespace absl {
+namespace test_internal {
+int BaseCountedInstance::num_instances_ = 0;
+int BaseCountedInstance::num_live_instances_ = 0;
+int BaseCountedInstance::num_moves_ = 0;
+int BaseCountedInstance::num_copies_ = 0;
+int BaseCountedInstance::num_swaps_ = 0;
+
+}  // namespace test_internal
+}  // namespace absl
diff --git a/absl/container/internal/test_instance_tracker.h b/absl/container/internal/test_instance_tracker.h
new file mode 100644
index 000000000000..cf8f3a531e62
--- /dev/null
+++ b/absl/container/internal/test_instance_tracker.h
@@ -0,0 +1,220 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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 ABSL_CONTAINER_INTERNAL_TEST_INSTANCE_TRACKER_H_
+#define ABSL_CONTAINER_INTERNAL_TEST_INSTANCE_TRACKER_H_
+
+#include <cstdlib>
+#include <ostream>
+
+namespace absl {
+namespace test_internal {
+
+// A type that counts number of occurences of the type, the live occurrences of
+// the type, as well as the number of copies, moves, and swaps that have
+// occurred on the type. This is used as a base class for the copyable,
+// copyable+movable, and movable types below that are used in actual tests. Use
+// InstanceTracker in tests to track the number of instances.
+class BaseCountedInstance {
+ public:
+  explicit BaseCountedInstance(int x) : value_(x) {
+    ++num_instances_;
+    ++num_live_instances_;
+  }
+  BaseCountedInstance(const BaseCountedInstance& x)
+      : value_(x.value_), is_live_(x.is_live_) {
+    ++num_instances_;
+    if (is_live_) ++num_live_instances_;
+    ++num_copies_;
+  }
+  BaseCountedInstance(BaseCountedInstance&& x)
+      : value_(x.value_), is_live_(x.is_live_) {
+    x.is_live_ = false;
+    ++num_instances_;
+    ++num_moves_;
+  }
+  ~BaseCountedInstance() {
+    --num_instances_;
+    if (is_live_) --num_live_instances_;
+  }
+
+  BaseCountedInstance& operator=(const BaseCountedInstance& x) {
+    value_ = x.value_;
+    if (is_live_) --num_live_instances_;
+    is_live_ = x.is_live_;
+    if (is_live_) ++num_live_instances_;
+    ++num_copies_;
+    return *this;
+  }
+  BaseCountedInstance& operator=(BaseCountedInstance&& x) {
+    value_ = x.value_;
+    if (is_live_) --num_live_instances_;
+    is_live_ = x.is_live_;
+    x.is_live_ = false;
+    ++num_moves_;
+    return *this;
+  }
+
+  int value() const {
+    if (!is_live_) std::abort();
+    return value_;
+  }
+
+  friend std::ostream& operator<<(std::ostream& o,
+                                  const BaseCountedInstance& v) {
+    return o << "[value:" << v.value() << "]";
+  }
+
+  // Implementation of efficient swap() that counts swaps.
+  static void SwapImpl(
+      BaseCountedInstance& lhs,    // NOLINT(runtime/references)
+      BaseCountedInstance& rhs) {  // NOLINT(runtime/references)
+    using std::swap;
+    swap(lhs.value_, rhs.value_);
+    swap(lhs.is_live_, rhs.is_live_);
+    ++BaseCountedInstance::num_swaps_;
+  }
+
+ private:
+  friend class InstanceTracker;
+
+  int value_;
+
+  // Indicates if the value is live, ie it hasn't been moved away from.
+  bool is_live_ = true;
+
+  // Number of instances.
+  static int num_instances_;
+
+  // Number of live instances (those that have not been moved away from.)
+  static int num_live_instances_;
+
+  // Number of times that BaseCountedInstance objects were moved.
+  static int num_moves_;
+
+  // Number of times that BaseCountedInstance objects were copied.
+  static int num_copies_;
+
+  // Number of times that BaseCountedInstance objects were swapped.
+  static int num_swaps_;
+};
+
+// Helper to track the BaseCountedInstance instance counters. Expects that the
+// number of instances and live_instances are the same when it is constructed
+// and when it is destructed.
+class InstanceTracker {
+ public:
+  InstanceTracker()
+      : start_instances_(BaseCountedInstance::num_instances_),
+        start_live_instances_(BaseCountedInstance::num_live_instances_) {
+    ResetCopiesMovesSwaps();
+  }
+  ~InstanceTracker() {
+    if (instances() != 0) std::abort();
+    if (live_instances() != 0) std::abort();
+  }
+
+  // Returns the number of BaseCountedInstance instances both containing valid
+  // values and those moved away from compared to when the InstanceTracker was
+  // constructed
+  int instances() const {
+    return BaseCountedInstance::num_instances_ - start_instances_;
+  }
+
+  // Returns the number of live BaseCountedInstance instances compared to when
+  // the InstanceTracker was constructed
+  int live_instances() const {
+    return BaseCountedInstance::num_live_instances_ - start_live_instances_;
+  }
+
+  // Returns the number of moves on BaseCountedInstance objects since
+  // construction or since the last call to ResetCopiesMovesSwaps().
+  int moves() const { return BaseCountedInstance::num_moves_ - start_moves_; }
+
+  // Returns the number of copies on BaseCountedInstance objects since
+  // construction or the last call to ResetCopiesMovesSwaps().
+  int copies() const {
+    return BaseCountedInstance::num_copies_ - start_copies_;
+  }
+
+  // Returns the number of swaps on BaseCountedInstance objects since
+  // construction or the last call to ResetCopiesMovesSwaps().
+  int swaps() const { return BaseCountedInstance::num_swaps_ - start_swaps_; }
+
+  // Resets the base values for moves, copies and swaps to the current values,
+  // so that subsequent Get*() calls for moves, copies and swaps will compare to
+  // the situation at the point of this call.
+  void ResetCopiesMovesSwaps() {
+    start_moves_ = BaseCountedInstance::num_moves_;
+    start_copies_ = BaseCountedInstance::num_copies_;
+    start_swaps_ = BaseCountedInstance::num_swaps_;
+  }
+
+ private:
+  int start_instances_;
+  int start_live_instances_;
+  int start_moves_;
+  int start_copies_;
+  int start_swaps_;
+};
+
+// Copyable, not movable.
+class CopyableOnlyInstance : public BaseCountedInstance {
+ public:
+  explicit CopyableOnlyInstance(int x) : BaseCountedInstance(x) {}
+  CopyableOnlyInstance(const CopyableOnlyInstance& rhs) = default;
+  CopyableOnlyInstance& operator=(const CopyableOnlyInstance& rhs) = default;
+
+  friend void swap(CopyableOnlyInstance& lhs, CopyableOnlyInstance& rhs) {
+    BaseCountedInstance::SwapImpl(lhs, rhs);
+  }
+
+  static bool supports_move() { return false; }
+};
+
+// Copyable and movable.
+class CopyableMovableInstance : public BaseCountedInstance {
+ public:
+  explicit CopyableMovableInstance(int x) : BaseCountedInstance(x) {}
+  CopyableMovableInstance(const CopyableMovableInstance& rhs) = default;
+  CopyableMovableInstance(CopyableMovableInstance&& rhs) = default;
+  CopyableMovableInstance& operator=(const CopyableMovableInstance& rhs) =
+      default;
+  CopyableMovableInstance& operator=(CopyableMovableInstance&& rhs) = default;
+
+  friend void swap(CopyableMovableInstance& lhs, CopyableMovableInstance& rhs) {
+    BaseCountedInstance::SwapImpl(lhs, rhs);
+  }
+
+  static bool supports_move() { return true; }
+};
+
+// Only movable, not default-constructible.
+class MovableOnlyInstance : public BaseCountedInstance {
+ public:
+  explicit MovableOnlyInstance(int x) : BaseCountedInstance(x) {}
+  MovableOnlyInstance(MovableOnlyInstance&& other) = default;
+  MovableOnlyInstance& operator=(MovableOnlyInstance&& other) = default;
+
+  friend void swap(MovableOnlyInstance& lhs, MovableOnlyInstance& rhs) {
+    BaseCountedInstance::SwapImpl(lhs, rhs);
+  }
+
+  static bool supports_move() { return true; }
+};
+
+}  // namespace test_internal
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INTERNAL_TEST_INSTANCE_TRACKER_H_
diff --git a/absl/container/internal/test_instance_tracker_test.cc b/absl/container/internal/test_instance_tracker_test.cc
new file mode 100644
index 000000000000..9efb6771cf08
--- /dev/null
+++ b/absl/container/internal/test_instance_tracker_test.cc
@@ -0,0 +1,160 @@
+// Copyright 2017 The Abseil Authors.
+//
+// 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 "absl/container/internal/test_instance_tracker.h"
+
+#include "gtest/gtest.h"
+
+namespace {
+
+using absl::test_internal::CopyableMovableInstance;
+using absl::test_internal::CopyableOnlyInstance;
+using absl::test_internal::InstanceTracker;
+using absl::test_internal::MovableOnlyInstance;
+
+TEST(TestInstanceTracker, CopyableMovable) {
+  InstanceTracker tracker;
+  CopyableMovableInstance src(1);
+  EXPECT_EQ(1, src.value()) << src;
+  CopyableMovableInstance copy(src);
+  CopyableMovableInstance move(std::move(src));
+  EXPECT_EQ(1, tracker.copies());
+  EXPECT_EQ(1, tracker.moves());
+  EXPECT_EQ(0, tracker.swaps());
+  EXPECT_EQ(3, tracker.instances());
+  EXPECT_EQ(2, tracker.live_instances());
+  tracker.ResetCopiesMovesSwaps();
+
+  CopyableMovableInstance copy_assign(1);
+  copy_assign = copy;
+  CopyableMovableInstance move_assign(1);
+  move_assign = std::move(move);
+  EXPECT_EQ(1, tracker.copies());
+  EXPECT_EQ(1, tracker.moves());
+  EXPECT_EQ(0, tracker.swaps());
+  EXPECT_EQ(5, tracker.instances());
+  EXPECT_EQ(3, tracker.live_instances());
+  tracker.ResetCopiesMovesSwaps();
+
+  {
+    using std::swap;
+    swap(move_assign, copy);
+    swap(copy, move_assign);
+    EXPECT_EQ(2, tracker.swaps());
+    EXPECT_EQ(0, tracker.copies());
+    EXPECT_EQ(0, tracker.moves());
+    EXPECT_EQ(5, tracker.instances());
+    EXPECT_EQ(3, tracker.live_instances());
+  }
+}
+
+TEST(TestInstanceTracker, CopyableOnly) {
+  InstanceTracker tracker;
+  CopyableOnlyInstance src(1);
+  EXPECT_EQ(1, src.value()) << src;
+  CopyableOnlyInstance copy(src);
+  CopyableOnlyInstance copy2(std::move(src));  // NOLINT
+  EXPECT_EQ(2, tracker.copies());
+  EXPECT_EQ(0, tracker.moves());
+  EXPECT_EQ(3, tracker.instances());
+  EXPECT_EQ(3, tracker.live_instances());
+  tracker.ResetCopiesMovesSwaps();
+
+  CopyableOnlyInstance copy_assign(1);
+  copy_assign = copy;
+  CopyableOnlyInstance copy_assign2(1);
+  copy_assign2 = std::move(copy2);  // NOLINT
+  EXPECT_EQ(2, tracker.copies());
+  EXPECT_EQ(0, tracker.moves());
+  EXPECT_EQ(5, tracker.instances());
+  EXPECT_EQ(5, tracker.live_instances());
+  tracker.ResetCopiesMovesSwaps();
+
+  {
+    using std::swap;
+    swap(src, copy);
+    swap(copy, src);
+    EXPECT_EQ(2, tracker.swaps());
+    EXPECT_EQ(0, tracker.copies());
+    EXPECT_EQ(0, tracker.moves());
+    EXPECT_EQ(5, tracker.instances());
+    EXPECT_EQ(5, tracker.live_instances());
+  }
+}
+
+TEST(TestInstanceTracker, MovableOnly) {
+  InstanceTracker tracker;
+  MovableOnlyInstance src(1);
+  EXPECT_EQ(1, src.value()) << src;
+  MovableOnlyInstance move(std::move(src));
+  MovableOnlyInstance move_assign(2);
+  move_assign = std::move(move);
+  EXPECT_EQ(3, tracker.instances());
+  EXPECT_EQ(1, tracker.live_instances());
+  EXPECT_EQ(2, tracker.moves());
+  EXPECT_EQ(0, tracker.copies());
+  tracker.ResetCopiesMovesSwaps();
+
+  {
+    using std::swap;
+    MovableOnlyInstance other(2);
+    swap(move_assign, other);
+    swap(other, move_assign);
+    EXPECT_EQ(2, tracker.swaps());
+    EXPECT_EQ(0, tracker.copies());
+    EXPECT_EQ(0, tracker.moves());
+    EXPECT_EQ(4, tracker.instances());
+    EXPECT_EQ(2, tracker.live_instances());
+  }
+}
+
+TEST(TestInstanceTracker, ExistingInstances) {
+  CopyableMovableInstance uncounted_instance(1);
+  CopyableMovableInstance uncounted_live_instance(
+      std::move(uncounted_instance));
+  InstanceTracker tracker;
+  EXPECT_EQ(0, tracker.instances());
+  EXPECT_EQ(0, tracker.live_instances());
+  EXPECT_EQ(0, tracker.copies());
+  {
+    CopyableMovableInstance instance1(1);
+    EXPECT_EQ(1, tracker.instances());
+    EXPECT_EQ(1, tracker.live_instances());
+    EXPECT_EQ(0, tracker.copies());
+    EXPECT_EQ(0, tracker.moves());
+    {
+      InstanceTracker tracker2;
+      CopyableMovableInstance instance2(instance1);
+      CopyableMovableInstance instance3(std::move(instance2));
+      EXPECT_EQ(3, tracker.instances());
+      EXPECT_EQ(2, tracker.live_instances());
+      EXPECT_EQ(1, tracker.copies());
+      EXPECT_EQ(1, tracker.moves());
+      EXPECT_EQ(2, tracker2.instances());
+      EXPECT_EQ(1, tracker2.live_instances());
+      EXPECT_EQ(1, tracker2.copies());
+      EXPECT_EQ(1, tracker2.moves());
+    }
+    EXPECT_EQ(1, tracker.instances());
+    EXPECT_EQ(1, tracker.live_instances());
+    EXPECT_EQ(1, tracker.copies());
+    EXPECT_EQ(1, tracker.moves());
+  }
+  EXPECT_EQ(0, tracker.instances());
+  EXPECT_EQ(0, tracker.live_instances());
+  EXPECT_EQ(1, tracker.copies());
+  EXPECT_EQ(1, tracker.moves());
+}
+
+}  // namespace