Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

8 files changed, 2279 insertions, 0 deletions

diff --git a/security/sandbox/chromium/base/containers/adapters.h b/security/sandbox/chromium/base/containers/adapters.h
new file mode 100644
index 0000000000..ec33481752
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/adapters.h
@@ -0,0 +1,55 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_ADAPTERS_H_
+#define BASE_CONTAINERS_ADAPTERS_H_
+
+#include <stddef.h>
+
+#include <iterator>
+#include <utility>
+
+#include "base/macros.h"
+
+namespace base {
+
+namespace internal {
+
+// Internal adapter class for implementing base::Reversed.
+template <typename T>
+class ReversedAdapter {
+ public:
+  using Iterator = decltype(std::rbegin(std::declval<T&>()));
+
+  explicit ReversedAdapter(T& t) : t_(t) {}
+  ReversedAdapter(const ReversedAdapter& ra) : t_(ra.t_) {}
+
+  Iterator begin() const { return std::rbegin(t_); }
+  Iterator end() const { return std::rend(t_); }
+
+ private:
+  T& t_;
+
+  DISALLOW_ASSIGN(ReversedAdapter);
+};
+
+}  // namespace internal
+
+// Reversed returns a container adapter usable in a range-based "for" statement
+// for iterating a reversible container in reverse order.
+//
+// Example:
+//
+//   std::vector<int> v = ...;
+//   for (int i : base::Reversed(v)) {
+//     // iterates through v from back to front
+//   }
+template <typename T>
+internal::ReversedAdapter<T> Reversed(T& t) {
+  return internal::ReversedAdapter<T>(t);
+}
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_ADAPTERS_H_
diff --git a/security/sandbox/chromium/base/containers/buffer_iterator.h b/security/sandbox/chromium/base/containers/buffer_iterator.h
new file mode 100644
index 0000000000..a4fd670190
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/buffer_iterator.h
@@ -0,0 +1,145 @@
+// Copyright 2019 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_BUFFER_ITERATOR_H_
+#define BASE_CONTAINERS_BUFFER_ITERATOR_H_
+
+#include <type_traits>
+
+#include "base/bit_cast.h"
+#include "base/containers/span.h"
+#include "base/numerics/checked_math.h"
+
+namespace base {
+
+// BufferIterator is a bounds-checked container utility to access variable-
+// length, heterogeneous structures contained within a buffer. If the data are
+// homogeneous, use base::span<> instead.
+//
+// After being created with a weakly-owned buffer, BufferIterator returns
+// pointers to structured data within the buffer. After each method call that
+// returns data in the buffer, the iterator position is advanced by the byte
+// size of the object (or span of objects) returned. If there are not enough
+// bytes remaining in the buffer to return the requested object(s), a nullptr
+// or empty span is returned.
+//
+// This class is similar to base::Pickle, which should be preferred for
+// serializing to disk. Pickle versions its header and does not support writing
+// structures, which are problematic for serialization due to struct padding and
+// version shear concerns.
+//
+// Example usage:
+//
+//    std::vector<uint8_t> buffer(4096);
+//    if (!ReadSomeData(&buffer, buffer.size())) {
+//      LOG(ERROR) << "Failed to read data.";
+//      return false;
+//    }
+//
+//    BufferIterator<uint8_t> iterator(buffer);
+//    uint32_t* num_items = iterator.Object<uint32_t>();
+//    if (!num_items) {
+//      LOG(ERROR) << "No num_items field."
+//      return false;
+//    }
+//
+//    base::span<const item_struct> items =
+//        iterator.Span<item_struct>(*num_items);
+//    if (items.size() != *num_items) {
+//      LOG(ERROR) << "Not enough items.";
+//      return false;
+//    }
+//
+//    // ... validate the objects in |items|.
+template <typename B>
+class BufferIterator {
+ public:
+  static_assert(std::is_same<std::remove_const_t<B>, char>::value ||
+                    std::is_same<std::remove_const_t<B>, unsigned char>::value,
+                "Underlying buffer type must be char-type.");
+
+  BufferIterator() {}
+  BufferIterator(B* data, size_t size)
+      : BufferIterator(make_span(data, size)) {}
+  explicit BufferIterator(span<B> buffer)
+      : buffer_(buffer), remaining_(buffer) {}
+  ~BufferIterator() {}
+
+  // Returns a pointer to a mutable structure T in the buffer at the current
+  // position. On success, the iterator position is advanced by sizeof(T). If
+  // there are not sizeof(T) bytes remaining in the buffer, returns nullptr.
+  template <typename T,
+            typename =
+                typename std::enable_if_t<std::is_trivially_copyable<T>::value>>
+  T* MutableObject() {
+    size_t size = sizeof(T);
+    size_t next_position;
+    if (!CheckAdd(position(), size).AssignIfValid(&next_position))
+      return nullptr;
+    if (next_position > total_size())
+      return nullptr;
+    T* t = bit_cast<T*>(remaining_.data());
+    remaining_ = remaining_.subspan(size);
+    return t;
+  }
+
+  // Returns a const pointer to an object of type T in the buffer at the current
+  // position.
+  template <typename T,
+            typename =
+                typename std::enable_if_t<std::is_trivially_copyable<T>::value>>
+  const T* Object() {
+    return MutableObject<const T>();
+  }
+
+  // Returns a span of |count| T objects in the buffer at the current position.
+  // On success, the iterator position is advanced by |sizeof(T) * count|. If
+  // there are not enough bytes remaining in the buffer to fulfill the request,
+  // returns an empty span.
+  template <typename T,
+            typename =
+                typename std::enable_if_t<std::is_trivially_copyable<T>::value>>
+  span<T> MutableSpan(size_t count) {
+    size_t size;
+    if (!CheckMul(sizeof(T), count).AssignIfValid(&size))
+      return span<T>();
+    size_t next_position;
+    if (!CheckAdd(position(), size).AssignIfValid(&next_position))
+      return span<T>();
+    if (next_position > total_size())
+      return span<T>();
+    auto result = span<T>(bit_cast<T*>(remaining_.data()), count);
+    remaining_ = remaining_.subspan(size);
+    return result;
+  }
+
+  // Returns a span to |count| const objects of type T in the buffer at the
+  // current position.
+  template <typename T,
+            typename =
+                typename std::enable_if_t<std::is_trivially_copyable<T>::value>>
+  span<const T> Span(size_t count) {
+    return MutableSpan<const T>(count);
+  }
+
+  // Resets the iterator position to the absolute offset |to|.
+  void Seek(size_t to) { remaining_ = buffer_.subspan(to); }
+
+  // Returns the total size of the underlying buffer.
+  size_t total_size() { return buffer_.size(); }
+
+  // Returns the current position in the buffer.
+  size_t position() { return buffer_.size_bytes() - remaining_.size_bytes(); }
+
+ private:
+  // The original buffer that the iterator was constructed with.
+  const span<B> buffer_;
+  // A subspan of |buffer_| containing the remaining bytes to iterate over.
+  span<B> remaining_;
+  // Copy and assign allowed.
+};
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_BUFFER_ITERATOR_H_
diff --git a/security/sandbox/chromium/base/containers/checked_iterators.h b/security/sandbox/chromium/base/containers/checked_iterators.h
new file mode 100644
index 0000000000..cdfd2909d4
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/checked_iterators.h
@@ -0,0 +1,205 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_CHECKED_ITERATORS_H_
+#define BASE_CONTAINERS_CHECKED_ITERATORS_H_
+
+#include <iterator>
+#include <memory>
+#include <type_traits>
+
+#include "base/containers/util.h"
+#include "base/logging.h"
+
+namespace base {
+
+template <typename T>
+class CheckedContiguousIterator {
+ public:
+  using difference_type = std::ptrdiff_t;
+  using value_type = std::remove_cv_t<T>;
+  using pointer = T*;
+  using reference = T&;
+  using iterator_category = std::random_access_iterator_tag;
+
+  // Required for converting constructor below.
+  template <typename U>
+  friend class CheckedContiguousIterator;
+
+  constexpr CheckedContiguousIterator() = default;
+  constexpr CheckedContiguousIterator(T* start, const T* end)
+      : CheckedContiguousIterator(start, start, end) {}
+  constexpr CheckedContiguousIterator(const T* start, T* current, const T* end)
+      : start_(start), current_(current), end_(end) {
+    CHECK_LE(start, current);
+    CHECK_LE(current, end);
+  }
+  constexpr CheckedContiguousIterator(const CheckedContiguousIterator& other) =
+      default;
+
+  // Converting constructor allowing conversions like CCI<T> to CCI<const T>,
+  // but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which
+  // are unsafe. Furthermore, this is the same condition as used by the
+  // converting constructors of std::span<T> and std::unique_ptr<T[]>.
+  // See https://wg21.link/n4042 for details.
+  template <
+      typename U,
+      std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr>
+  constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other)
+      : start_(other.start_), current_(other.current_), end_(other.end_) {
+    // We explicitly don't delegate to the 3-argument constructor here. Its
+    // CHECKs would be redundant, since we expect |other| to maintain its own
+    // invariant. However, DCHECKs never hurt anybody. Presumably.
+    DCHECK_LE(other.start_, other.current_);
+    DCHECK_LE(other.current_, other.end_);
+  }
+
+  ~CheckedContiguousIterator() = default;
+
+  constexpr CheckedContiguousIterator& operator=(
+      const CheckedContiguousIterator& other) = default;
+
+  constexpr bool operator==(const CheckedContiguousIterator& other) const {
+    CheckComparable(other);
+    return current_ == other.current_;
+  }
+
+  constexpr bool operator!=(const CheckedContiguousIterator& other) const {
+    CheckComparable(other);
+    return current_ != other.current_;
+  }
+
+  constexpr bool operator<(const CheckedContiguousIterator& other) const {
+    CheckComparable(other);
+    return current_ < other.current_;
+  }
+
+  constexpr bool operator<=(const CheckedContiguousIterator& other) const {
+    CheckComparable(other);
+    return current_ <= other.current_;
+  }
+
+  constexpr bool operator>(const CheckedContiguousIterator& other) const {
+    CheckComparable(other);
+    return current_ > other.current_;
+  }
+
+  constexpr bool operator>=(const CheckedContiguousIterator& other) const {
+    CheckComparable(other);
+    return current_ >= other.current_;
+  }
+
+  constexpr CheckedContiguousIterator& operator++() {
+    CHECK_NE(current_, end_);
+    ++current_;
+    return *this;
+  }
+
+  constexpr CheckedContiguousIterator operator++(int) {
+    CheckedContiguousIterator old = *this;
+    ++*this;
+    return old;
+  }
+
+  constexpr CheckedContiguousIterator& operator--() {
+    CHECK_NE(current_, start_);
+    --current_;
+    return *this;
+  }
+
+  constexpr CheckedContiguousIterator operator--(int) {
+    CheckedContiguousIterator old = *this;
+    --*this;
+    return old;
+  }
+
+  constexpr CheckedContiguousIterator& operator+=(difference_type rhs) {
+    if (rhs > 0) {
+      CHECK_LE(rhs, end_ - current_);
+    } else {
+      CHECK_LE(-rhs, current_ - start_);
+    }
+    current_ += rhs;
+    return *this;
+  }
+
+  constexpr CheckedContiguousIterator operator+(difference_type rhs) const {
+    CheckedContiguousIterator it = *this;
+    it += rhs;
+    return it;
+  }
+
+  constexpr CheckedContiguousIterator& operator-=(difference_type rhs) {
+    if (rhs < 0) {
+      CHECK_LE(-rhs, end_ - current_);
+    } else {
+      CHECK_LE(rhs, current_ - start_);
+    }
+    current_ -= rhs;
+    return *this;
+  }
+
+  constexpr CheckedContiguousIterator operator-(difference_type rhs) const {
+    CheckedContiguousIterator it = *this;
+    it -= rhs;
+    return it;
+  }
+
+  constexpr friend difference_type operator-(
+      const CheckedContiguousIterator& lhs,
+      const CheckedContiguousIterator& rhs) {
+    CHECK_EQ(lhs.start_, rhs.start_);
+    CHECK_EQ(lhs.end_, rhs.end_);
+    return lhs.current_ - rhs.current_;
+  }
+
+  constexpr reference operator*() const {
+    CHECK_NE(current_, end_);
+    return *current_;
+  }
+
+  constexpr pointer operator->() const {
+    CHECK_NE(current_, end_);
+    return current_;
+  }
+
+  constexpr reference operator[](difference_type rhs) const {
+    CHECK_GE(rhs, 0);
+    CHECK_LT(rhs, end_ - current_);
+    return current_[rhs];
+  }
+
+  static bool IsRangeMoveSafe(const CheckedContiguousIterator& from_begin,
+                              const CheckedContiguousIterator& from_end,
+                              const CheckedContiguousIterator& to)
+      WARN_UNUSED_RESULT {
+    if (from_end < from_begin)
+      return false;
+    const auto from_begin_uintptr = get_uintptr(from_begin.current_);
+    const auto from_end_uintptr = get_uintptr(from_end.current_);
+    const auto to_begin_uintptr = get_uintptr(to.current_);
+    const auto to_end_uintptr =
+        get_uintptr((to + std::distance(from_begin, from_end)).current_);
+
+    return to_begin_uintptr >= from_end_uintptr ||
+           to_end_uintptr <= from_begin_uintptr;
+  }
+
+ private:
+  constexpr void CheckComparable(const CheckedContiguousIterator& other) const {
+    CHECK_EQ(start_, other.start_);
+    CHECK_EQ(end_, other.end_);
+  }
+
+  const T* start_ = nullptr;
+  T* current_ = nullptr;
+  const T* end_ = nullptr;
+};
+
+template <typename T>
+using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>;
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_CHECKED_ITERATORS_H_
diff --git a/security/sandbox/chromium/base/containers/circular_deque.h b/security/sandbox/chromium/base/containers/circular_deque.h
new file mode 100644
index 0000000000..0d452b56be
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/circular_deque.h
@@ -0,0 +1,1112 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_CIRCULAR_DEQUE_H_
+#define BASE_CONTAINERS_CIRCULAR_DEQUE_H_
+
+#include <algorithm>
+#include <cstddef>
+#include <iterator>
+#include <type_traits>
+#include <utility>
+
+#include "base/containers/vector_buffer.h"
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/stl_util.h"
+#include "base/template_util.h"
+
+// base::circular_deque is similar to std::deque. Unlike std::deque, the
+// storage is provided in a flat circular buffer conceptually similar to a
+// vector. The beginning and end will wrap around as necessary so that
+// pushes and pops will be constant time as long as a capacity expansion is
+// not required.
+//
+// The API should be identical to std::deque with the following differences:
+//
+//  - ITERATORS ARE NOT STABLE. Mutating the container will invalidate all
+//    iterators.
+//
+//  - Insertions may resize the vector and so are not constant time (std::deque
+//    guarantees constant time for insertions at the ends).
+//
+//  - Container-wide comparisons are not implemented. If you want to compare
+//    two containers, use an algorithm so the expensive iteration is explicit.
+//
+// If you want a similar container with only a queue API, use base::queue in
+// base/containers/queue.h.
+//
+// Constructors:
+//   circular_deque();
+//   circular_deque(size_t count);
+//   circular_deque(size_t count, const T& value);
+//   circular_deque(InputIterator first, InputIterator last);
+//   circular_deque(const circular_deque&);
+//   circular_deque(circular_deque&&);
+//   circular_deque(std::initializer_list<value_type>);
+//
+// Assignment functions:
+//   circular_deque& operator=(const circular_deque&);
+//   circular_deque& operator=(circular_deque&&);
+//   circular_deque& operator=(std::initializer_list<T>);
+//   void assign(size_t count, const T& value);
+//   void assign(InputIterator first, InputIterator last);
+//   void assign(std::initializer_list<T> value);
+//
+// Random accessors:
+//   T& at(size_t);
+//   const T& at(size_t) const;
+//   T& operator[](size_t);
+//   const T& operator[](size_t) const;
+//
+// End accessors:
+//   T& front();
+//   const T& front() const;
+//   T& back();
+//   const T& back() const;
+//
+// Iterator functions:
+//   iterator               begin();
+//   const_iterator         begin() const;
+//   const_iterator         cbegin() const;
+//   iterator               end();
+//   const_iterator         end() const;
+//   const_iterator         cend() const;
+//   reverse_iterator       rbegin();
+//   const_reverse_iterator rbegin() const;
+//   const_reverse_iterator crbegin() const;
+//   reverse_iterator       rend();
+//   const_reverse_iterator rend() const;
+//   const_reverse_iterator crend() const;
+//
+// Memory management:
+//   void reserve(size_t);  // SEE IMPLEMENTATION FOR SOME GOTCHAS.
+//   size_t capacity() const;
+//   void shrink_to_fit();
+//
+// Size management:
+//   void clear();
+//   bool empty() const;
+//   size_t size() const;
+//   void resize(size_t);
+//   void resize(size_t count, const T& value);
+//
+// Positional insert and erase:
+//   void insert(const_iterator pos, size_type count, const T& value);
+//   void insert(const_iterator pos,
+//               InputIterator first, InputIterator last);
+//   iterator insert(const_iterator pos, const T& value);
+//   iterator insert(const_iterator pos, T&& value);
+//   iterator emplace(const_iterator pos, Args&&... args);
+//   iterator erase(const_iterator pos);
+//   iterator erase(const_iterator first, const_iterator last);
+//
+// End insert and erase:
+//   void push_front(const T&);
+//   void push_front(T&&);
+//   void push_back(const T&);
+//   void push_back(T&&);
+//   T& emplace_front(Args&&...);
+//   T& emplace_back(Args&&...);
+//   void pop_front();
+//   void pop_back();
+//
+// General:
+//   void swap(circular_deque&);
+
+namespace base {
+
+template <class T>
+class circular_deque;
+
+namespace internal {
+
+// Start allocating nonempty buffers with this many entries. This is the
+// external capacity so the internal buffer will be one larger (= 4) which is
+// more even for the allocator. See the descriptions of internal vs. external
+// capacity on the comment above the buffer_ variable below.
+constexpr size_t kCircularBufferInitialCapacity = 3;
+
+template <typename T>
+class circular_deque_const_iterator {
+ public:
+  using difference_type = std::ptrdiff_t;
+  using value_type = T;
+  using pointer = const T*;
+  using reference = const T&;
+  using iterator_category = std::random_access_iterator_tag;
+
+  circular_deque_const_iterator() : parent_deque_(nullptr), index_(0) {
+#if DCHECK_IS_ON()
+    created_generation_ = 0;
+#endif  // DCHECK_IS_ON()
+  }
+
+  // Dereferencing.
+  const T& operator*() const {
+    CheckUnstableUsage();
+    parent_deque_->CheckValidIndex(index_);
+    return parent_deque_->buffer_[index_];
+  }
+  const T* operator->() const {
+    CheckUnstableUsage();
+    parent_deque_->CheckValidIndex(index_);
+    return &parent_deque_->buffer_[index_];
+  }
+  const value_type& operator[](difference_type i) const { return *(*this + i); }
+
+  // Increment and decrement.
+  circular_deque_const_iterator& operator++() {
+    Increment();
+    return *this;
+  }
+  circular_deque_const_iterator operator++(int) {
+    circular_deque_const_iterator ret = *this;
+    Increment();
+    return ret;
+  }
+  circular_deque_const_iterator& operator--() {
+    Decrement();
+    return *this;
+  }
+  circular_deque_const_iterator operator--(int) {
+    circular_deque_const_iterator ret = *this;
+    Decrement();
+    return ret;
+  }
+
+  // Random access mutation.
+  friend circular_deque_const_iterator operator+(
+      const circular_deque_const_iterator& iter,
+      difference_type offset) {
+    circular_deque_const_iterator ret = iter;
+    ret.Add(offset);
+    return ret;
+  }
+  circular_deque_const_iterator& operator+=(difference_type offset) {
+    Add(offset);
+    return *this;
+  }
+  friend circular_deque_const_iterator operator-(
+      const circular_deque_const_iterator& iter,
+      difference_type offset) {
+    circular_deque_const_iterator ret = iter;
+    ret.Add(-offset);
+    return ret;
+  }
+  circular_deque_const_iterator& operator-=(difference_type offset) {
+    Add(-offset);
+    return *this;
+  }
+
+  friend std::ptrdiff_t operator-(const circular_deque_const_iterator& lhs,
+                                  const circular_deque_const_iterator& rhs) {
+    lhs.CheckComparable(rhs);
+    return lhs.OffsetFromBegin() - rhs.OffsetFromBegin();
+  }
+
+  // Comparisons.
+  friend bool operator==(const circular_deque_const_iterator& lhs,
+                         const circular_deque_const_iterator& rhs) {
+    lhs.CheckComparable(rhs);
+    return lhs.index_ == rhs.index_;
+  }
+  friend bool operator!=(const circular_deque_const_iterator& lhs,
+                         const circular_deque_const_iterator& rhs) {
+    return !(lhs == rhs);
+  }
+  friend bool operator<(const circular_deque_const_iterator& lhs,
+                        const circular_deque_const_iterator& rhs) {
+    lhs.CheckComparable(rhs);
+    return lhs.OffsetFromBegin() < rhs.OffsetFromBegin();
+  }
+  friend bool operator<=(const circular_deque_const_iterator& lhs,
+                         const circular_deque_const_iterator& rhs) {
+    return !(lhs > rhs);
+  }
+  friend bool operator>(const circular_deque_const_iterator& lhs,
+                        const circular_deque_const_iterator& rhs) {
+    lhs.CheckComparable(rhs);
+    return lhs.OffsetFromBegin() > rhs.OffsetFromBegin();
+  }
+  friend bool operator>=(const circular_deque_const_iterator& lhs,
+                         const circular_deque_const_iterator& rhs) {
+    return !(lhs < rhs);
+  }
+
+ protected:
+  friend class circular_deque<T>;
+
+  circular_deque_const_iterator(const circular_deque<T>* parent, size_t index)
+      : parent_deque_(parent), index_(index) {
+#if DCHECK_IS_ON()
+    created_generation_ = parent->generation_;
+#endif  // DCHECK_IS_ON()
+  }
+
+  // Returns the offset from the beginning index of the buffer to the current
+  // item.
+  size_t OffsetFromBegin() const {
+    if (index_ >= parent_deque_->begin_)
+      return index_ - parent_deque_->begin_;  // On the same side as begin.
+    return parent_deque_->buffer_.capacity() - parent_deque_->begin_ + index_;
+  }
+
+  // Most uses will be ++ and -- so use a simplified implementation.
+  void Increment() {
+    CheckUnstableUsage();
+    parent_deque_->CheckValidIndex(index_);
+    index_++;
+    if (index_ == parent_deque_->buffer_.capacity())
+      index_ = 0;
+  }
+  void Decrement() {
+    CheckUnstableUsage();
+    parent_deque_->CheckValidIndexOrEnd(index_);
+    if (index_ == 0)
+      index_ = parent_deque_->buffer_.capacity() - 1;
+    else
+      index_--;
+  }
+  void Add(difference_type delta) {
+    CheckUnstableUsage();
+#if DCHECK_IS_ON()
+    if (delta <= 0)
+      parent_deque_->CheckValidIndexOrEnd(index_);
+    else
+      parent_deque_->CheckValidIndex(index_);
+#endif
+    // It should be valid to add 0 to any iterator, even if the container is
+    // empty and the iterator points to end(). The modulo below will divide
+    // by 0 if the buffer capacity is empty, so it's important to check for
+    // this case explicitly.
+    if (delta == 0)
+      return;
+
+    difference_type new_offset = OffsetFromBegin() + delta;
+    DCHECK(new_offset >= 0 &&
+           new_offset <= static_cast<difference_type>(parent_deque_->size()));
+    index_ = (new_offset + parent_deque_->begin_) %
+             parent_deque_->buffer_.capacity();
+  }
+
+#if DCHECK_IS_ON()
+  void CheckUnstableUsage() const {
+    DCHECK(parent_deque_);
+    // Since circular_deque doesn't guarantee stability, any attempt to
+    // dereference this iterator after a mutation (i.e. the generation doesn't
+    // match the original) in the container is illegal.
+    DCHECK_EQ(created_generation_, parent_deque_->generation_)
+        << "circular_deque iterator dereferenced after mutation.";
+  }
+  void CheckComparable(const circular_deque_const_iterator& other) const {
+    DCHECK_EQ(parent_deque_, other.parent_deque_);
+    // Since circular_deque doesn't guarantee stability, two iterators that
+    // are compared must have been generated without mutating the container.
+    // If this fires, the container was mutated between generating the two
+    // iterators being compared.
+    DCHECK_EQ(created_generation_, other.created_generation_);
+  }
+#else
+  inline void CheckUnstableUsage() const {}
+  inline void CheckComparable(const circular_deque_const_iterator&) const {}
+#endif  // DCHECK_IS_ON()
+
+  const circular_deque<T>* parent_deque_;
+  size_t index_;
+
+#if DCHECK_IS_ON()
+  // The generation of the parent deque when this iterator was created. The
+  // container will update the generation for every modification so we can
+  // test if the container was modified by comparing them.
+  uint64_t created_generation_;
+#endif  // DCHECK_IS_ON()
+};
+
+template <typename T>
+class circular_deque_iterator : public circular_deque_const_iterator<T> {
+  using base = circular_deque_const_iterator<T>;
+
+ public:
+  friend class circular_deque<T>;
+
+  using difference_type = std::ptrdiff_t;
+  using value_type = T;
+  using pointer = T*;
+  using reference = T&;
+  using iterator_category = std::random_access_iterator_tag;
+
+  // Expose the base class' constructor.
+  circular_deque_iterator() : circular_deque_const_iterator<T>() {}
+
+  // Dereferencing.
+  T& operator*() const { return const_cast<T&>(base::operator*()); }
+  T* operator->() const { return const_cast<T*>(base::operator->()); }
+  T& operator[](difference_type i) {
+    return const_cast<T&>(base::operator[](i));
+  }
+
+  // Random access mutation.
+  friend circular_deque_iterator operator+(const circular_deque_iterator& iter,
+                                           difference_type offset) {
+    circular_deque_iterator ret = iter;
+    ret.Add(offset);
+    return ret;
+  }
+  circular_deque_iterator& operator+=(difference_type offset) {
+    base::Add(offset);
+    return *this;
+  }
+  friend circular_deque_iterator operator-(const circular_deque_iterator& iter,
+                                           difference_type offset) {
+    circular_deque_iterator ret = iter;
+    ret.Add(-offset);
+    return ret;
+  }
+  circular_deque_iterator& operator-=(difference_type offset) {
+    base::Add(-offset);
+    return *this;
+  }
+
+  // Increment and decrement.
+  circular_deque_iterator& operator++() {
+    base::Increment();
+    return *this;
+  }
+  circular_deque_iterator operator++(int) {
+    circular_deque_iterator ret = *this;
+    base::Increment();
+    return ret;
+  }
+  circular_deque_iterator& operator--() {
+    base::Decrement();
+    return *this;
+  }
+  circular_deque_iterator operator--(int) {
+    circular_deque_iterator ret = *this;
+    base::Decrement();
+    return ret;
+  }
+
+ private:
+  circular_deque_iterator(const circular_deque<T>* parent, size_t index)
+      : circular_deque_const_iterator<T>(parent, index) {}
+};
+
+}  // namespace internal
+
+template <typename T>
+class circular_deque {
+ private:
+  using VectorBuffer = internal::VectorBuffer<T>;
+
+ public:
+  using value_type = T;
+  using size_type = std::size_t;
+  using difference_type = std::ptrdiff_t;
+  using reference = value_type&;
+  using const_reference = const value_type&;
+  using pointer = value_type*;
+  using const_pointer = const value_type*;
+
+  using iterator = internal::circular_deque_iterator<T>;
+  using const_iterator = internal::circular_deque_const_iterator<T>;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  // ---------------------------------------------------------------------------
+  // Constructor
+
+  constexpr circular_deque() = default;
+
+  // Constructs with |count| copies of |value| or default constructed version.
+  circular_deque(size_type count) { resize(count); }
+  circular_deque(size_type count, const T& value) { resize(count, value); }
+
+  // Range constructor.
+  template <class InputIterator>
+  circular_deque(InputIterator first, InputIterator last) {
+    assign(first, last);
+  }
+
+  // Copy/move.
+  circular_deque(const circular_deque& other) : buffer_(other.size() + 1) {
+    assign(other.begin(), other.end());
+  }
+  circular_deque(circular_deque&& other) noexcept
+      : buffer_(std::move(other.buffer_)),
+        begin_(other.begin_),
+        end_(other.end_) {
+    other.begin_ = 0;
+    other.end_ = 0;
+  }
+
+  circular_deque(std::initializer_list<value_type> init) { assign(init); }
+
+  ~circular_deque() { DestructRange(begin_, end_); }
+
+  // ---------------------------------------------------------------------------
+  // Assignments.
+  //
+  // All of these may invalidate iterators and references.
+
+  circular_deque& operator=(const circular_deque& other) {
+    if (&other == this)
+      return *this;
+
+    reserve(other.size());
+    assign(other.begin(), other.end());
+    return *this;
+  }
+  circular_deque& operator=(circular_deque&& other) noexcept {
+    if (&other == this)
+      return *this;
+
+    // We're about to overwrite the buffer, so don't free it in clear to
+    // avoid doing it twice.
+    ClearRetainCapacity();
+    buffer_ = std::move(other.buffer_);
+    begin_ = other.begin_;
+    end_ = other.end_;
+
+    other.begin_ = 0;
+    other.end_ = 0;
+
+    IncrementGeneration();
+    return *this;
+  }
+  circular_deque& operator=(std::initializer_list<value_type> ilist) {
+    reserve(ilist.size());
+    assign(std::begin(ilist), std::end(ilist));
+    return *this;
+  }
+
+  void assign(size_type count, const value_type& value) {
+    ClearRetainCapacity();
+    reserve(count);
+    for (size_t i = 0; i < count; i++)
+      emplace_back(value);
+    IncrementGeneration();
+  }
+
+  // This variant should be enabled only when InputIterator is an iterator.
+  template <typename InputIterator>
+  typename std::enable_if<::base::internal::is_iterator<InputIterator>::value,
+                          void>::type
+  assign(InputIterator first, InputIterator last) {
+    // Possible future enhancement, dispatch on iterator tag type. For forward
+    // iterators we can use std::difference to preallocate the space required
+    // and only do one copy.
+    ClearRetainCapacity();
+    for (; first != last; ++first)
+      emplace_back(*first);
+    IncrementGeneration();
+  }
+
+  void assign(std::initializer_list<value_type> value) {
+    reserve(std::distance(value.begin(), value.end()));
+    assign(value.begin(), value.end());
+  }
+
+  // ---------------------------------------------------------------------------
+  // Accessors.
+  //
+  // Since this class assumes no exceptions, at() and operator[] are equivalent.
+
+  const value_type& at(size_type i) const {
+    DCHECK(i < size());
+    size_t right_size = buffer_.capacity() - begin_;
+    if (begin_ <= end_ || i < right_size)
+      return buffer_[begin_ + i];
+    return buffer_[i - right_size];
+  }
+  value_type& at(size_type i) {
+    return const_cast<value_type&>(as_const(*this).at(i));
+  }
+
+  value_type& operator[](size_type i) {
+    return const_cast<value_type&>(as_const(*this)[i]);
+  }
+
+  const value_type& operator[](size_type i) const { return at(i); }
+
+  value_type& front() {
+    DCHECK(!empty());
+    return buffer_[begin_];
+  }
+  const value_type& front() const {
+    DCHECK(!empty());
+    return buffer_[begin_];
+  }
+
+  value_type& back() {
+    DCHECK(!empty());
+    return *(--end());
+  }
+  const value_type& back() const {
+    DCHECK(!empty());
+    return *(--end());
+  }
+
+  // ---------------------------------------------------------------------------
+  // Iterators.
+
+  iterator begin() { return iterator(this, begin_); }
+  const_iterator begin() const { return const_iterator(this, begin_); }
+  const_iterator cbegin() const { return const_iterator(this, begin_); }
+
+  iterator end() { return iterator(this, end_); }
+  const_iterator end() const { return const_iterator(this, end_); }
+  const_iterator cend() const { return const_iterator(this, end_); }
+
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+  const_reverse_iterator crbegin() const { return rbegin(); }
+
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
+  const_reverse_iterator crend() const { return rend(); }
+
+  // ---------------------------------------------------------------------------
+  // Memory management.
+
+  // IMPORTANT NOTE ON reserve(...): This class implements auto-shrinking of
+  // the buffer when elements are deleted and there is "too much" wasted space.
+  // So if you call reserve() with a large size in anticipation of pushing many
+  // elements, but pop an element before the queue is full, the capacity you
+  // reserved may be lost.
+  //
+  // As a result, it's only worthwhile to call reserve() when you're adding
+  // many things at once with no intermediate operations.
+  void reserve(size_type new_capacity) {
+    if (new_capacity > capacity())
+      SetCapacityTo(new_capacity);
+  }
+
+  size_type capacity() const {
+    // One item is wasted to indicate end().
+    return buffer_.capacity() == 0 ? 0 : buffer_.capacity() - 1;
+  }
+
+  void shrink_to_fit() {
+    if (empty()) {
+      // Optimize empty case to really delete everything if there was
+      // something.
+      if (buffer_.capacity())
+        buffer_ = VectorBuffer();
+    } else {
+      SetCapacityTo(size());
+    }
+  }
+
+  // ---------------------------------------------------------------------------
+  // Size management.
+
+  // This will additionally reset the capacity() to 0.
+  void clear() {
+    // This can't resize(0) because that requires a default constructor to
+    // compile, which not all contained classes may implement.
+    ClearRetainCapacity();
+    buffer_ = VectorBuffer();
+  }
+
+  bool empty() const { return begin_ == end_; }
+
+  size_type size() const {
+    if (begin_ <= end_)
+      return end_ - begin_;
+    return buffer_.capacity() - begin_ + end_;
+  }
+
+  // When reducing size, the elements are deleted from the end. When expanding
+  // size, elements are added to the end with |value| or the default
+  // constructed version. Even when using resize(count) to shrink, a default
+  // constructor is required for the code to compile, even though it will not
+  // be called.
+  //
+  // There are two versions rather than using a default value to avoid
+  // creating a temporary when shrinking (when it's not needed). Plus if
+  // the default constructor is desired when expanding usually just calling it
+  // for each element is faster than making a default-constructed temporary and
+  // copying it.
+  void resize(size_type count) {
+    // SEE BELOW VERSION if you change this. The code is mostly the same.
+    if (count > size()) {
+      // This could be slighly more efficient but expanding a queue with
+      // identical elements is unusual and the extra computations of emplacing
+      // one-by-one will typically be small relative to calling the constructor
+      // for every item.
+      ExpandCapacityIfNecessary(count - size());
+      while (size() < count)
+        emplace_back();
+    } else if (count < size()) {
+      size_t new_end = (begin_ + count) % buffer_.capacity();
+      DestructRange(new_end, end_);
+      end_ = new_end;
+
+      ShrinkCapacityIfNecessary();
+    }
+    IncrementGeneration();
+  }
+  void resize(size_type count, const value_type& value) {
+    // SEE ABOVE VERSION if you change this. The code is mostly the same.
+    if (count > size()) {
+      ExpandCapacityIfNecessary(count - size());
+      while (size() < count)
+        emplace_back(value);
+    } else if (count < size()) {
+      size_t new_end = (begin_ + count) % buffer_.capacity();
+      DestructRange(new_end, end_);
+      end_ = new_end;
+
+      ShrinkCapacityIfNecessary();
+    }
+    IncrementGeneration();
+  }
+
+  // ---------------------------------------------------------------------------
+  // Insert and erase.
+  //
+  // Insertion and deletion in the middle is O(n) and invalidates all existing
+  // iterators.
+  //
+  // The implementation of insert isn't optimized as much as it could be. If
+  // the insertion requires that the buffer be grown, it will first be grown
+  // and everything moved, and then the items will be inserted, potentially
+  // moving some items twice. This simplifies the implemntation substantially
+  // and means less generated templatized code. Since this is an uncommon
+  // operation for deques, and already relatively slow, it doesn't seem worth
+  // the benefit to optimize this.
+
+  void insert(const_iterator pos, size_type count, const T& value) {
+    ValidateIterator(pos);
+
+    // Optimize insert at the beginning.
+    if (pos == begin()) {
+      ExpandCapacityIfNecessary(count);
+      for (size_t i = 0; i < count; i++)
+        push_front(value);
+      return;
+    }
+
+    iterator insert_cur(this, pos.index_);
+    iterator insert_end;
+    MakeRoomFor(count, &insert_cur, &insert_end);
+    while (insert_cur < insert_end) {
+      new (&buffer_[insert_cur.index_]) T(value);
+      ++insert_cur;
+    }
+
+    IncrementGeneration();
+  }
+
+  // This enable_if keeps this call from getting confused with the (pos, count,
+  // value) version when value is an integer.
+  template <class InputIterator>
+  typename std::enable_if<::base::internal::is_iterator<InputIterator>::value,
+                          void>::type
+  insert(const_iterator pos, InputIterator first, InputIterator last) {
+    ValidateIterator(pos);
+
+    size_t inserted_items = std::distance(first, last);
+    if (inserted_items == 0)
+      return;  // Can divide by 0 when doing modulo below, so return early.
+
+    // Make a hole to copy the items into.
+    iterator insert_cur;
+    iterator insert_end;
+    if (pos == begin()) {
+      // Optimize insert at the beginning, nothing needs to be shifted and the
+      // hole is the |inserted_items| block immediately before |begin_|.
+      ExpandCapacityIfNecessary(inserted_items);
+      insert_end = begin();
+      begin_ =
+          (begin_ + buffer_.capacity() - inserted_items) % buffer_.capacity();
+      insert_cur = begin();
+    } else {
+      insert_cur = iterator(this, pos.index_);
+      MakeRoomFor(inserted_items, &insert_cur, &insert_end);
+    }
+
+    // Copy the items.
+    while (insert_cur < insert_end) {
+      new (&buffer_[insert_cur.index_]) T(*first);
+      ++insert_cur;
+      ++first;
+    }
+
+    IncrementGeneration();
+  }
+
+  // These all return an iterator to the inserted item. Existing iterators will
+  // be invalidated.
+  iterator insert(const_iterator pos, const T& value) {
+    return emplace(pos, value);
+  }
+  iterator insert(const_iterator pos, T&& value) {
+    return emplace(pos, std::move(value));
+  }
+  template <class... Args>
+  iterator emplace(const_iterator pos, Args&&... args) {
+    ValidateIterator(pos);
+
+    // Optimize insert at beginning which doesn't require shifting.
+    if (pos == cbegin()) {
+      emplace_front(std::forward<Args>(args)...);
+      return begin();
+    }
+
+    // Do this before we make the new iterators we return.
+    IncrementGeneration();
+
+    iterator insert_begin(this, pos.index_);
+    iterator insert_end;
+    MakeRoomFor(1, &insert_begin, &insert_end);
+    new (&buffer_[insert_begin.index_]) T(std::forward<Args>(args)...);
+
+    return insert_begin;
+  }
+
+  // Calling erase() won't automatically resize the buffer smaller like resize
+  // or the pop functions. Erase is slow and relatively uncommon, and for
+  // normal deque usage a pop will normally be done on a regular basis that
+  // will prevent excessive buffer usage over long periods of time. It's not
+  // worth having the extra code for every template instantiation of erase()
+  // to resize capacity downward to a new buffer.
+  iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
+  iterator erase(const_iterator first, const_iterator last) {
+    ValidateIterator(first);
+    ValidateIterator(last);
+
+    IncrementGeneration();
+
+    // First, call the destructor on the deleted items.
+    if (first.index_ == last.index_) {
+      // Nothing deleted. Need to return early to avoid falling through to
+      // moving items on top of themselves.
+      return iterator(this, first.index_);
+    } else if (first.index_ < last.index_) {
+      // Contiguous range.
+      buffer_.DestructRange(&buffer_[first.index_], &buffer_[last.index_]);
+    } else {
+      // Deleted range wraps around.
+      buffer_.DestructRange(&buffer_[first.index_],
+                            &buffer_[buffer_.capacity()]);
+      buffer_.DestructRange(&buffer_[0], &buffer_[last.index_]);
+    }
+
+    if (first.index_ == begin_) {
+      // This deletion is from the beginning. Nothing needs to be copied, only
+      // begin_ needs to be updated.
+      begin_ = last.index_;
+      return iterator(this, last.index_);
+    }
+
+    // In an erase operation, the shifted items all move logically to the left,
+    // so move them from left-to-right.
+    iterator move_src(this, last.index_);
+    iterator move_src_end = end();
+    iterator move_dest(this, first.index_);
+    for (; move_src < move_src_end; move_src++, move_dest++) {
+      buffer_.MoveRange(&buffer_[move_src.index_],
+                        &buffer_[move_src.index_ + 1],
+                        &buffer_[move_dest.index_]);
+    }
+
+    end_ = move_dest.index_;
+
+    // Since we did not reallocate and only changed things after the erase
+    // element(s), the input iterator's index points to the thing following the
+    // deletion.
+    return iterator(this, first.index_);
+  }
+
+  // ---------------------------------------------------------------------------
+  // Begin/end operations.
+
+  void push_front(const T& value) { emplace_front(value); }
+  void push_front(T&& value) { emplace_front(std::move(value)); }
+
+  void push_back(const T& value) { emplace_back(value); }
+  void push_back(T&& value) { emplace_back(std::move(value)); }
+
+  template <class... Args>
+  reference emplace_front(Args&&... args) {
+    ExpandCapacityIfNecessary(1);
+    if (begin_ == 0)
+      begin_ = buffer_.capacity() - 1;
+    else
+      begin_--;
+    IncrementGeneration();
+    new (&buffer_[begin_]) T(std::forward<Args>(args)...);
+    return front();
+  }
+
+  template <class... Args>
+  reference emplace_back(Args&&... args) {
+    ExpandCapacityIfNecessary(1);
+    new (&buffer_[end_]) T(std::forward<Args>(args)...);
+    if (end_ == buffer_.capacity() - 1)
+      end_ = 0;
+    else
+      end_++;
+    IncrementGeneration();
+    return back();
+  }
+
+  void pop_front() {
+    DCHECK(size());
+    buffer_.DestructRange(&buffer_[begin_], &buffer_[begin_ + 1]);
+    begin_++;
+    if (begin_ == buffer_.capacity())
+      begin_ = 0;
+
+    ShrinkCapacityIfNecessary();
+
+    // Technically popping will not invalidate any iterators since the
+    // underlying buffer will be stable. But in the future we may want to add a
+    // feature that resizes the buffer smaller if there is too much wasted
+    // space. This ensures we can make such a change safely.
+    IncrementGeneration();
+  }
+  void pop_back() {
+    DCHECK(size());
+    if (end_ == 0)
+      end_ = buffer_.capacity() - 1;
+    else
+      end_--;
+    buffer_.DestructRange(&buffer_[end_], &buffer_[end_ + 1]);
+
+    ShrinkCapacityIfNecessary();
+
+    // See pop_front comment about why this is here.
+    IncrementGeneration();
+  }
+
+  // ---------------------------------------------------------------------------
+  // General operations.
+
+  void swap(circular_deque& other) {
+    std::swap(buffer_, other.buffer_);
+    std::swap(begin_, other.begin_);
+    std::swap(end_, other.end_);
+    IncrementGeneration();
+  }
+
+  friend void swap(circular_deque& lhs, circular_deque& rhs) { lhs.swap(rhs); }
+
+ private:
+  friend internal::circular_deque_iterator<T>;
+  friend internal::circular_deque_const_iterator<T>;
+
+  // Moves the items in the given circular buffer to the current one. The
+  // source is moved from so will become invalid. The destination buffer must
+  // have already been allocated with enough size.
+  static void MoveBuffer(VectorBuffer& from_buf,
+                         size_t from_begin,
+                         size_t from_end,
+                         VectorBuffer* to_buf,
+                         size_t* to_begin,
+                         size_t* to_end) {
+    size_t from_capacity = from_buf.capacity();
+
+    *to_begin = 0;
+    if (from_begin < from_end) {
+      // Contiguous.
+      from_buf.MoveRange(&from_buf[from_begin], &from_buf[from_end],
+                         to_buf->begin());
+      *to_end = from_end - from_begin;
+    } else if (from_begin > from_end) {
+      // Discontiguous, copy the right side to the beginning of the new buffer.
+      from_buf.MoveRange(&from_buf[from_begin], &from_buf[from_capacity],
+                         to_buf->begin());
+      size_t right_size = from_capacity - from_begin;
+      // Append the left side.
+      from_buf.MoveRange(&from_buf[0], &from_buf[from_end],
+                         &(*to_buf)[right_size]);
+      *to_end = right_size + from_end;
+    } else {
+      // No items.
+      *to_end = 0;
+    }
+  }
+
+  // Expands the buffer size. This assumes the size is larger than the
+  // number of elements in the vector (it won't call delete on anything).
+  void SetCapacityTo(size_t new_capacity) {
+    // Use the capacity + 1 as the internal buffer size to differentiate
+    // empty and full (see definition of buffer_ below).
+    VectorBuffer new_buffer(new_capacity + 1);
+    MoveBuffer(buffer_, begin_, end_, &new_buffer, &begin_, &end_);
+    buffer_ = std::move(new_buffer);
+  }
+  void ExpandCapacityIfNecessary(size_t additional_elts) {
+    size_t min_new_capacity = size() + additional_elts;
+    if (capacity() >= min_new_capacity)
+      return;  // Already enough room.
+
+    min_new_capacity =
+        std::max(min_new_capacity, internal::kCircularBufferInitialCapacity);
+
+    // std::vector always grows by at least 50%. WTF::Deque grows by at least
+    // 25%. We expect queue workloads to generally stay at a similar size and
+    // grow less than a vector might, so use 25%.
+    size_t new_capacity =
+        std::max(min_new_capacity, capacity() + capacity() / 4);
+    SetCapacityTo(new_capacity);
+  }
+
+  void ShrinkCapacityIfNecessary() {
+    // Don't auto-shrink below this size.
+    if (capacity() <= internal::kCircularBufferInitialCapacity)
+      return;
+
+    // Shrink when 100% of the size() is wasted.
+    size_t sz = size();
+    size_t empty_spaces = capacity() - sz;
+    if (empty_spaces < sz)
+      return;
+
+    // Leave 1/4 the size as free capacity, not going below the initial
+    // capacity.
+    size_t new_capacity =
+        std::max(internal::kCircularBufferInitialCapacity, sz + sz / 4);
+    if (new_capacity < capacity()) {
+      // Count extra item to convert to internal capacity.
+      SetCapacityTo(new_capacity);
+    }
+  }
+
+  // Backend for clear() but does not resize the internal buffer.
+  void ClearRetainCapacity() {
+    // This can't resize(0) because that requires a default constructor to
+    // compile, which not all contained classes may implement.
+    DestructRange(begin_, end_);
+    begin_ = 0;
+    end_ = 0;
+    IncrementGeneration();
+  }
+
+  // Calls destructors for the given begin->end indices. The indices may wrap
+  // around. The buffer is not resized, and the begin_ and end_ members are
+  // not changed.
+  void DestructRange(size_t begin, size_t end) {
+    if (end == begin) {
+      return;
+    } else if (end > begin) {
+      buffer_.DestructRange(&buffer_[begin], &buffer_[end]);
+    } else {
+      buffer_.DestructRange(&buffer_[begin], &buffer_[buffer_.capacity()]);
+      buffer_.DestructRange(&buffer_[0], &buffer_[end]);
+    }
+  }
+
+  // Makes room for |count| items starting at |*insert_begin|. Since iterators
+  // are not stable across buffer resizes, |*insert_begin| will be updated to
+  // point to the beginning of the newly opened position in the new array (it's
+  // in/out), and the end of the newly opened position (it's out-only).
+  void MakeRoomFor(size_t count, iterator* insert_begin, iterator* insert_end) {
+    if (count == 0) {
+      *insert_end = *insert_begin;
+      return;
+    }
+
+    // The offset from the beginning will be stable across reallocations.
+    size_t begin_offset = insert_begin->OffsetFromBegin();
+    ExpandCapacityIfNecessary(count);
+
+    insert_begin->index_ = (begin_ + begin_offset) % buffer_.capacity();
+    *insert_end =
+        iterator(this, (insert_begin->index_ + count) % buffer_.capacity());
+
+    // Update the new end and prepare the iterators for copying.
+    iterator src = end();
+    end_ = (end_ + count) % buffer_.capacity();
+    iterator dest = end();
+
+    // Move the elements. This will always involve shifting logically to the
+    // right, so move in a right-to-left order.
+    while (true) {
+      if (src == *insert_begin)
+        break;
+      --src;
+      --dest;
+      buffer_.MoveRange(&buffer_[src.index_], &buffer_[src.index_ + 1],
+                        &buffer_[dest.index_]);
+    }
+  }
+
+#if DCHECK_IS_ON()
+  // Asserts the given index is dereferencable. The index is an index into the
+  // buffer, not an index used by operator[] or at() which will be offsets from
+  // begin.
+  void CheckValidIndex(size_t i) const {
+    if (begin_ <= end_)
+      DCHECK(i >= begin_ && i < end_);
+    else
+      DCHECK((i >= begin_ && i < buffer_.capacity()) || i < end_);
+  }
+
+  // Asserts the given index is either dereferencable or points to end().
+  void CheckValidIndexOrEnd(size_t i) const {
+    if (i != end_)
+      CheckValidIndex(i);
+  }
+
+  void ValidateIterator(const const_iterator& i) const {
+    DCHECK(i.parent_deque_ == this);
+    i.CheckUnstableUsage();
+  }
+
+  // See generation_ below.
+  void IncrementGeneration() { generation_++; }
+#else
+  // No-op versions of these functions for release builds.
+  void CheckValidIndex(size_t) const {}
+  void CheckValidIndexOrEnd(size_t) const {}
+  void ValidateIterator(const const_iterator& i) const {}
+  void IncrementGeneration() {}
+#endif
+
+  // Danger, the buffer_.capacity() is the "internal capacity" which is
+  // capacity() + 1 since there is an extra item to indicate the end. Otherwise
+  // being completely empty and completely full are indistinguishable (begin ==
+  // end). We could add a separate flag to avoid it, but that adds significant
+  // extra complexity since every computation will have to check for it. Always
+  // keeping one extra unused element in the buffer makes iterator computations
+  // much simpler.
+  //
+  // Container internal code will want to use buffer_.capacity() for offset
+  // computations rather than capacity().
+  VectorBuffer buffer_;
+  size_type begin_ = 0;
+  size_type end_ = 0;
+
+#if DCHECK_IS_ON()
+  // Incremented every time a modification is made that could affect iterator
+  // invalidations.
+  uint64_t generation_ = 0;
+#endif
+};
+
+// Implementations of base::Erase[If] (see base/stl_util.h).
+template <class T, class Value>
+void Erase(circular_deque<T>& container, const Value& value) {
+  container.erase(std::remove(container.begin(), container.end(), value),
+                  container.end());
+}
+
+template <class T, class Predicate>
+void EraseIf(circular_deque<T>& container, Predicate pred) {
+  container.erase(std::remove_if(container.begin(), container.end(), pred),
+                  container.end());
+}
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_CIRCULAR_DEQUE_H_
diff --git a/security/sandbox/chromium/base/containers/span.h b/security/sandbox/chromium/base/containers/span.h
new file mode 100644
index 0000000000..ce2e3c47e5
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/span.h
@@ -0,0 +1,530 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_SPAN_H_
+#define BASE_CONTAINERS_SPAN_H_
+
+#include <stddef.h>
+
+#include <algorithm>
+#include <array>
+#include <iterator>
+#include <limits>
+#include <type_traits>
+#include <utility>
+
+#include "base/containers/checked_iterators.h"
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/stl_util.h"
+
+namespace base {
+
+// [views.constants]
+constexpr size_t dynamic_extent = std::numeric_limits<size_t>::max();
+
+template <typename T, size_t Extent = dynamic_extent>
+class span;
+
+namespace internal {
+
+template <typename T>
+struct ExtentImpl : std::integral_constant<size_t, dynamic_extent> {};
+
+template <typename T, size_t N>
+struct ExtentImpl<T[N]> : std::integral_constant<size_t, N> {};
+
+template <typename T, size_t N>
+struct ExtentImpl<std::array<T, N>> : std::integral_constant<size_t, N> {};
+
+template <typename T, size_t N>
+struct ExtentImpl<base::span<T, N>> : std::integral_constant<size_t, N> {};
+
+template <typename T>
+using Extent = ExtentImpl<std::remove_cv_t<std::remove_reference_t<T>>>;
+
+template <typename T>
+struct IsSpanImpl : std::false_type {};
+
+template <typename T, size_t Extent>
+struct IsSpanImpl<span<T, Extent>> : std::true_type {};
+
+template <typename T>
+using IsSpan = IsSpanImpl<std::decay_t<T>>;
+
+template <typename T>
+struct IsStdArrayImpl : std::false_type {};
+
+template <typename T, size_t N>
+struct IsStdArrayImpl<std::array<T, N>> : std::true_type {};
+
+template <typename T>
+using IsStdArray = IsStdArrayImpl<std::decay_t<T>>;
+
+template <typename T>
+using IsCArray = std::is_array<std::remove_reference_t<T>>;
+
+template <typename From, typename To>
+using IsLegalDataConversion = std::is_convertible<From (*)[], To (*)[]>;
+
+template <typename Container, typename T>
+using ContainerHasConvertibleData = IsLegalDataConversion<
+    std::remove_pointer_t<decltype(base::data(std::declval<Container>()))>,
+    T>;
+
+template <typename Container>
+using ContainerHasIntegralSize =
+    std::is_integral<decltype(base::size(std::declval<Container>()))>;
+
+template <typename From, size_t FromExtent, typename To, size_t ToExtent>
+using EnableIfLegalSpanConversion =
+    std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) &&
+                     IsLegalDataConversion<From, To>::value>;
+
+// SFINAE check if Array can be converted to a span<T>.
+template <typename Array, typename T, size_t Extent>
+using EnableIfSpanCompatibleArray =
+    std::enable_if_t<(Extent == dynamic_extent ||
+                      Extent == internal::Extent<Array>::value) &&
+                     ContainerHasConvertibleData<Array, T>::value>;
+
+// SFINAE check if Container can be converted to a span<T>.
+template <typename Container, typename T>
+using IsSpanCompatibleContainer =
+    std::conditional_t<!IsSpan<Container>::value &&
+                           !IsStdArray<Container>::value &&
+                           !IsCArray<Container>::value &&
+                           ContainerHasConvertibleData<Container, T>::value &&
+                           ContainerHasIntegralSize<Container>::value,
+                       std::true_type,
+                       std::false_type>;
+
+template <typename Container, typename T>
+using EnableIfSpanCompatibleContainer =
+    std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value>;
+
+template <typename Container, typename T, size_t Extent>
+using EnableIfSpanCompatibleContainerAndSpanIsDynamic =
+    std::enable_if_t<IsSpanCompatibleContainer<Container, T>::value &&
+                     Extent == dynamic_extent>;
+
+// A helper template for storing the size of a span. Spans with static extents
+// don't require additional storage, since the extent itself is specified in the
+// template parameter.
+template <size_t Extent>
+class ExtentStorage {
+ public:
+  constexpr explicit ExtentStorage(size_t size) noexcept {}
+  constexpr size_t size() const noexcept { return Extent; }
+};
+
+// Specialization of ExtentStorage for dynamic extents, which do require
+// explicit storage for the size.
+template <>
+struct ExtentStorage<dynamic_extent> {
+  constexpr explicit ExtentStorage(size_t size) noexcept : size_(size) {}
+  constexpr size_t size() const noexcept { return size_; }
+
+ private:
+  size_t size_;
+};
+
+}  // namespace internal
+
+// A span is a value type that represents an array of elements of type T. Since
+// it only consists of a pointer to memory with an associated size, it is very
+// light-weight. It is cheap to construct, copy, move and use spans, so that
+// users are encouraged to use it as a pass-by-value parameter. A span does not
+// own the underlying memory, so care must be taken to ensure that a span does
+// not outlive the backing store.
+//
+// span is somewhat analogous to StringPiece, but with arbitrary element types,
+// allowing mutation if T is non-const.
+//
+// span is implicitly convertible from C++ arrays, as well as most [1]
+// container-like types that provide a data() and size() method (such as
+// std::vector<T>). A mutable span<T> can also be implicitly converted to an
+// immutable span<const T>.
+//
+// Consider using a span for functions that take a data pointer and size
+// parameter: it allows the function to still act on an array-like type, while
+// allowing the caller code to be a bit more concise.
+//
+// For read-only data access pass a span<const T>: the caller can supply either
+// a span<const T> or a span<T>, while the callee will have a read-only view.
+// For read-write access a mutable span<T> is required.
+//
+// Without span:
+//   Read-Only:
+//     // std::string HexEncode(const uint8_t* data, size_t size);
+//     std::vector<uint8_t> data_buffer = GenerateData();
+//     std::string r = HexEncode(data_buffer.data(), data_buffer.size());
+//
+//  Mutable:
+//     // ssize_t SafeSNPrintf(char* buf, size_t N, const char* fmt, Args...);
+//     char str_buffer[100];
+//     SafeSNPrintf(str_buffer, sizeof(str_buffer), "Pi ~= %lf", 3.14);
+//
+// With span:
+//   Read-Only:
+//     // std::string HexEncode(base::span<const uint8_t> data);
+//     std::vector<uint8_t> data_buffer = GenerateData();
+//     std::string r = HexEncode(data_buffer);
+//
+//  Mutable:
+//     // ssize_t SafeSNPrintf(base::span<char>, const char* fmt, Args...);
+//     char str_buffer[100];
+//     SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14);
+//
+// Spans with "const" and pointers
+// -------------------------------
+//
+// Const and pointers can get confusing. Here are vectors of pointers and their
+// corresponding spans:
+//
+//   const std::vector<int*>        =>  base::span<int* const>
+//   std::vector<const int*>        =>  base::span<const int*>
+//   const std::vector<const int*>  =>  base::span<const int* const>
+//
+// Differences from the C++20 draft
+// --------------------------------
+//
+// http://eel.is/c++draft/views contains the latest C++20 draft of std::span.
+// Chromium tries to follow the draft as close as possible. Differences between
+// the draft and the implementation are documented in subsections below.
+//
+// Differences from [span.objectrep]:
+// - as_bytes() and as_writable_bytes() return spans of uint8_t instead of
+//   std::byte (std::byte is a C++17 feature)
+//
+// Differences from [span.cons]:
+// - Constructing a static span (i.e. Extent != dynamic_extent) from a dynamic
+//   sized container (e.g. std::vector) requires an explicit conversion (in the
+//   C++20 draft this is simply UB)
+//
+// Differences from [span.obs]:
+// - empty() is marked with WARN_UNUSED_RESULT instead of [[nodiscard]]
+//   ([[nodiscard]] is a C++17 feature)
+//
+// Furthermore, all constructors and methods are marked noexcept due to the lack
+// of exceptions in Chromium.
+//
+// Due to the lack of class template argument deduction guides in C++14
+// appropriate make_span() utility functions are provided.
+
+// [span], class template span
+template <typename T, size_t Extent>
+class span : public internal::ExtentStorage<Extent> {
+ private:
+  using ExtentStorage = internal::ExtentStorage<Extent>;
+
+ public:
+  using element_type = T;
+  using value_type = std::remove_cv_t<T>;
+  using size_type = size_t;
+  using difference_type = ptrdiff_t;
+  using pointer = T*;
+  using reference = T&;
+  using iterator = CheckedContiguousIterator<T>;
+  using const_iterator = CheckedContiguousConstIterator<T>;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  static constexpr size_t extent = Extent;
+
+  // [span.cons], span constructors, copy, assignment, and destructor
+  constexpr span() noexcept : ExtentStorage(0), data_(nullptr) {
+    static_assert(Extent == dynamic_extent || Extent == 0, "Invalid Extent");
+  }
+
+  constexpr span(T* data, size_t size) noexcept
+      : ExtentStorage(size), data_(data) {
+    CHECK(Extent == dynamic_extent || Extent == size);
+  }
+
+  // Artificially templatized to break ambiguity for span(ptr, 0).
+  template <typename = void>
+  constexpr span(T* begin, T* end) noexcept : span(begin, end - begin) {
+    // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
+    CHECK(begin <= end);
+  }
+
+  template <
+      size_t N,
+      typename = internal::EnableIfSpanCompatibleArray<T (&)[N], T, Extent>>
+  constexpr span(T (&array)[N]) noexcept : span(base::data(array), N) {}
+
+  template <
+      size_t N,
+      typename = internal::
+          EnableIfSpanCompatibleArray<std::array<value_type, N>&, T, Extent>>
+  constexpr span(std::array<value_type, N>& array) noexcept
+      : span(base::data(array), N) {}
+
+  template <size_t N,
+            typename = internal::EnableIfSpanCompatibleArray<
+                const std::array<value_type, N>&,
+                T,
+                Extent>>
+  constexpr span(const std::array<value_type, N>& array) noexcept
+      : span(base::data(array), N) {}
+
+  // Conversion from a container that has compatible base::data() and integral
+  // base::size().
+  template <
+      typename Container,
+      typename =
+          internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic<Container&,
+                                                                    T,
+                                                                    Extent>>
+  constexpr span(Container& container) noexcept
+      : span(base::data(container), base::size(container)) {}
+
+  template <
+      typename Container,
+      typename = internal::EnableIfSpanCompatibleContainerAndSpanIsDynamic<
+          const Container&,
+          T,
+          Extent>>
+  constexpr span(const Container& container) noexcept
+      : span(base::data(container), base::size(container)) {}
+
+  constexpr span(const span& other) noexcept = default;
+
+  // Conversions from spans of compatible types and extents: this allows a
+  // span<T> to be seamlessly used as a span<const T>, but not the other way
+  // around. If extent is not dynamic, OtherExtent has to be equal to Extent.
+  template <
+      typename U,
+      size_t OtherExtent,
+      typename =
+          internal::EnableIfLegalSpanConversion<U, OtherExtent, T, Extent>>
+  constexpr span(const span<U, OtherExtent>& other)
+      : span(other.data(), other.size()) {}
+
+  constexpr span& operator=(const span& other) noexcept = default;
+  ~span() noexcept = default;
+
+  // [span.sub], span subviews
+  template <size_t Count>
+  constexpr span<T, Count> first() const noexcept {
+    static_assert(Extent == dynamic_extent || Count <= Extent,
+                  "Count must not exceed Extent");
+    CHECK(Extent != dynamic_extent || Count <= size());
+    return {data(), Count};
+  }
+
+  template <size_t Count>
+  constexpr span<T, Count> last() const noexcept {
+    static_assert(Extent == dynamic_extent || Count <= Extent,
+                  "Count must not exceed Extent");
+    CHECK(Extent != dynamic_extent || Count <= size());
+    return {data() + (size() - Count), Count};
+  }
+
+  template <size_t Offset, size_t Count = dynamic_extent>
+  constexpr span<T,
+                 (Count != dynamic_extent
+                      ? Count
+                      : (Extent != dynamic_extent ? Extent - Offset
+                                                  : dynamic_extent))>
+  subspan() const noexcept {
+    static_assert(Extent == dynamic_extent || Offset <= Extent,
+                  "Offset must not exceed Extent");
+    static_assert(Extent == dynamic_extent || Count == dynamic_extent ||
+                      Count <= Extent - Offset,
+                  "Count must not exceed Extent - Offset");
+    CHECK(Extent != dynamic_extent || Offset <= size());
+    CHECK(Extent != dynamic_extent || Count == dynamic_extent ||
+          Count <= size() - Offset);
+    return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset};
+  }
+
+  constexpr span<T, dynamic_extent> first(size_t count) const noexcept {
+    // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
+    CHECK(count <= size());
+    return {data(), count};
+  }
+
+  constexpr span<T, dynamic_extent> last(size_t count) const noexcept {
+    // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
+    CHECK(count <= size());
+    return {data() + (size() - count), count};
+  }
+
+  constexpr span<T, dynamic_extent> subspan(size_t offset,
+                                            size_t count = dynamic_extent) const
+      noexcept {
+    // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
+    CHECK(offset <= size());
+    CHECK(count == dynamic_extent || count <= size() - offset);
+    return {data() + offset, count != dynamic_extent ? count : size() - offset};
+  }
+
+  // [span.obs], span observers
+  constexpr size_t size() const noexcept { return ExtentStorage::size(); }
+  constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); }
+  constexpr bool empty() const noexcept WARN_UNUSED_RESULT {
+    return size() == 0;
+  }
+
+  // [span.elem], span element access
+  constexpr T& operator[](size_t idx) const noexcept {
+    // Note: CHECK_LT is not constexpr, hence regular CHECK must be used.
+    CHECK(idx < size());
+    return *(data() + idx);
+  }
+
+  constexpr T& front() const noexcept {
+    static_assert(Extent == dynamic_extent || Extent > 0,
+                  "Extent must not be 0");
+    CHECK(Extent != dynamic_extent || !empty());
+    return *data();
+  }
+
+  constexpr T& back() const noexcept {
+    static_assert(Extent == dynamic_extent || Extent > 0,
+                  "Extent must not be 0");
+    CHECK(Extent != dynamic_extent || !empty());
+    return *(data() + size() - 1);
+  }
+
+  constexpr T* data() const noexcept { return data_; }
+
+  // [span.iter], span iterator support
+  constexpr iterator begin() const noexcept {
+    return iterator(data_, data_ + size());
+  }
+  constexpr iterator end() const noexcept {
+    return iterator(data_, data_ + size(), data_ + size());
+  }
+
+  constexpr const_iterator cbegin() const noexcept { return begin(); }
+  constexpr const_iterator cend() const noexcept { return end(); }
+
+  constexpr reverse_iterator rbegin() const noexcept {
+    return reverse_iterator(end());
+  }
+  constexpr reverse_iterator rend() const noexcept {
+    return reverse_iterator(begin());
+  }
+
+  constexpr const_reverse_iterator crbegin() const noexcept {
+    return const_reverse_iterator(cend());
+  }
+  constexpr const_reverse_iterator crend() const noexcept {
+    return const_reverse_iterator(cbegin());
+  }
+
+ private:
+  T* data_;
+};
+
+// span<T, Extent>::extent can not be declared inline prior to C++17, hence this
+// definition is required.
+template <class T, size_t Extent>
+constexpr size_t span<T, Extent>::extent;
+
+// [span.objectrep], views of object representation
+template <typename T, size_t X>
+span<const uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)>
+as_bytes(span<T, X> s) noexcept {
+  return {reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes()};
+}
+
+template <typename T,
+          size_t X,
+          typename = std::enable_if_t<!std::is_const<T>::value>>
+span<uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)>
+as_writable_bytes(span<T, X> s) noexcept {
+  return {reinterpret_cast<uint8_t*>(s.data()), s.size_bytes()};
+}
+
+// Type-deducing helpers for constructing a span.
+template <int&... ExplicitArgumentBarrier, typename T>
+constexpr span<T> make_span(T* data, size_t size) noexcept {
+  return {data, size};
+}
+
+template <int&... ExplicitArgumentBarrier, typename T>
+constexpr span<T> make_span(T* begin, T* end) noexcept {
+  return {begin, end};
+}
+
+// make_span utility function that deduces both the span's value_type and extent
+// from the passed in argument.
+//
+// Usage: auto span = base::make_span(...);
+template <int&... ExplicitArgumentBarrier, typename Container>
+constexpr auto make_span(Container&& container) noexcept {
+  using T =
+      std::remove_pointer_t<decltype(base::data(std::declval<Container>()))>;
+  using Extent = internal::Extent<Container>;
+  return span<T, Extent::value>(std::forward<Container>(container));
+}
+
+// make_span utility function that allows callers to explicit specify the span's
+// extent, the value_type is deduced automatically. This is useful when passing
+// a dynamically sized container to a method expecting static spans, when the
+// container is known to have the correct size.
+//
+// Note: This will CHECK that N indeed matches size(container).
+//
+// Usage: auto static_span = base::make_span<N>(...);
+template <size_t N, int&... ExplicitArgumentBarrier, typename Container>
+constexpr auto make_span(Container&& container) noexcept {
+  using T =
+      std::remove_pointer_t<decltype(base::data(std::declval<Container>()))>;
+  return span<T, N>(base::data(container), base::size(container));
+}
+
+}  // namespace base
+
+// Note: std::tuple_size, std::tuple_element and std::get are specialized for
+// static spans, so that they can be used in C++17's structured bindings. While
+// we don't support C++17 yet, there is no harm in providing these
+// specializations already.
+namespace std {
+
+// [span.tuple], tuple interface
+#if defined(__clang__)
+// Due to https://llvm.org/PR39871 and https://llvm.org/PR41331 and their
+// respective fixes different versions of libc++ declare std::tuple_size and
+// std::tuple_element either as classes or structs. In order to be able to
+// specialize std::tuple_size and std::tuple_element for custom base types we
+// thus need to disable -Wmismatched-tags in order to support all build
+// configurations. Note that this is blessed by the standard in
+// https://timsong-cpp.github.io/cppwp/n4140/dcl.type.elab#3.
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wmismatched-tags"
+#endif
+template <typename T, size_t X>
+struct tuple_size<base::span<T, X>> : public integral_constant<size_t, X> {};
+
+template <typename T>
+struct tuple_size<base::span<T, base::dynamic_extent>>;  // not defined
+
+template <size_t I, typename T, size_t X>
+struct tuple_element<I, base::span<T, X>> {
+  static_assert(
+      base::dynamic_extent != X,
+      "std::tuple_element<> not supported for base::span<T, dynamic_extent>");
+  static_assert(I < X,
+                "Index out of bounds in std::tuple_element<> (base::span)");
+  using type = T;
+};
+#if defined(__clang__)
+#pragma clang diagnostic pop  // -Wmismatched-tags
+#endif
+
+template <size_t I, typename T, size_t X>
+constexpr T& get(base::span<T, X> s) noexcept {
+  static_assert(base::dynamic_extent != X,
+                "std::get<> not supported for base::span<T, dynamic_extent>");
+  static_assert(I < X, "Index out of bounds in std::get<> (base::span)");
+  return s[I];
+}
+
+}  // namespace std
+
+#endif  // BASE_CONTAINERS_SPAN_H_
diff --git a/security/sandbox/chromium/base/containers/stack.h b/security/sandbox/chromium/base/containers/stack.h
new file mode 100644
index 0000000000..5cf06f8251
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/stack.h
@@ -0,0 +1,23 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_STACK_H_
+#define BASE_CONTAINERS_STACK_H_
+
+#include <stack>
+
+#include "base/containers/circular_deque.h"
+
+namespace base {
+
+// Provides a definition of base::stack that's like std::stack but uses a
+// base::circular_deque instead of std::deque. Since std::stack is just a
+// wrapper for an underlying type, we can just provide a typedef for it that
+// defaults to the base circular_deque.
+template <class T, class Container = circular_deque<T>>
+using stack = std::stack<T, Container>;
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_STACK_H_
diff --git a/security/sandbox/chromium/base/containers/util.h b/security/sandbox/chromium/base/containers/util.h
new file mode 100644
index 0000000000..435db0d1f8
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/util.h
@@ -0,0 +1,21 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_UTIL_H_
+#define BASE_CONTAINERS_UTIL_H_
+
+#include <stdint.h>
+
+namespace base {
+
+// TODO(crbug.com/817982): What we really need is for checked_math.h to be
+// able to do checked arithmetic on pointers.
+template <typename T>
+static inline uintptr_t get_uintptr(const T* t) {
+  return reinterpret_cast<uintptr_t>(t);
+}
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_UTIL_H_
diff --git a/security/sandbox/chromium/base/containers/vector_buffer.h b/security/sandbox/chromium/base/containers/vector_buffer.h
new file mode 100644
index 0000000000..83cd2ac139
--- /dev/null
+++ b/security/sandbox/chromium/base/containers/vector_buffer.h
@@ -0,0 +1,188 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_CONTAINERS_VECTOR_BUFFERS_H_
+#define BASE_CONTAINERS_VECTOR_BUFFERS_H_
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <type_traits>
+#include <utility>
+
+#include "base/containers/util.h"
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/numerics/checked_math.h"
+
+namespace base {
+namespace internal {
+
+// Internal implementation detail of base/containers.
+//
+// Implements a vector-like buffer that holds a certain capacity of T. Unlike
+// std::vector, VectorBuffer never constructs or destructs its arguments, and
+// can't change sizes. But it does implement templates to assist in efficient
+// moving and destruction of those items manually.
+//
+// In particular, the destructor function does not iterate over the items if
+// there is no destructor. Moves should be implemented as a memcpy/memmove for
+// trivially copyable objects (POD) otherwise, it should be a std::move if
+// possible, and as a last resort it falls back to a copy. This behavior is
+// similar to std::vector.
+//
+// No special consideration is done for noexcept move constructors since
+// we compile without exceptions.
+//
+// The current API does not support moving overlapping ranges.
+template <typename T>
+class VectorBuffer {
+ public:
+  constexpr VectorBuffer() = default;
+
+#if defined(__clang__) && !defined(__native_client__)
+  // This constructor converts an uninitialized void* to a T* which triggers
+  // clang Control Flow Integrity. Since this is as-designed, disable.
+  __attribute__((no_sanitize("cfi-unrelated-cast", "vptr")))
+#endif
+  VectorBuffer(size_t count)
+      : buffer_(reinterpret_cast<T*>(
+            malloc(CheckMul(sizeof(T), count).ValueOrDie()))),
+        capacity_(count) {
+  }
+  VectorBuffer(VectorBuffer&& other) noexcept
+      : buffer_(other.buffer_), capacity_(other.capacity_) {
+    other.buffer_ = nullptr;
+    other.capacity_ = 0;
+  }
+
+  ~VectorBuffer() { free(buffer_); }
+
+  VectorBuffer& operator=(VectorBuffer&& other) {
+    free(buffer_);
+    buffer_ = other.buffer_;
+    capacity_ = other.capacity_;
+
+    other.buffer_ = nullptr;
+    other.capacity_ = 0;
+    return *this;
+  }
+
+  size_t capacity() const { return capacity_; }
+
+  T& operator[](size_t i) {
+    // TODO(crbug.com/817982): Some call sites (at least circular_deque.h) are
+    // calling this with `i == capacity_` as a way of getting `end()`. Therefore
+    // we have to allow this for now (`i <= capacity_`), until we fix those call
+    // sites to use real iterators. This comment applies here and to `const T&
+    // operator[]`, below.
+    CHECK_LE(i, capacity_);
+    return buffer_[i];
+  }
+
+  const T& operator[](size_t i) const {
+    CHECK_LE(i, capacity_);
+    return buffer_[i];
+  }
+
+  T* begin() { return buffer_; }
+  T* end() { return &buffer_[capacity_]; }
+
+  // DestructRange ------------------------------------------------------------
+
+  // Trivially destructible objects need not have their destructors called.
+  template <typename T2 = T,
+            typename std::enable_if<std::is_trivially_destructible<T2>::value,
+                                    int>::type = 0>
+  void DestructRange(T* begin, T* end) {}
+
+  // Non-trivially destructible objects must have their destructors called
+  // individually.
+  template <typename T2 = T,
+            typename std::enable_if<!std::is_trivially_destructible<T2>::value,
+                                    int>::type = 0>
+  void DestructRange(T* begin, T* end) {
+    CHECK_LE(begin, end);
+    while (begin != end) {
+      begin->~T();
+      begin++;
+    }
+  }
+
+  // MoveRange ----------------------------------------------------------------
+  //
+  // The destructor will be called (as necessary) for all moved types. The
+  // ranges must not overlap.
+  //
+  // The parameters and begin and end (one past the last) of the input buffer,
+  // and the address of the first element to copy to. There must be sufficient
+  // room in the destination for all items in the range [begin, end).
+
+  // Trivially copyable types can use memcpy. trivially copyable implies
+  // that there is a trivial destructor as we don't have to call it.
+  template <typename T2 = T,
+            typename std::enable_if<base::is_trivially_copyable<T2>::value,
+                                    int>::type = 0>
+  static void MoveRange(T* from_begin, T* from_end, T* to) {
+    CHECK(!RangesOverlap(from_begin, from_end, to));
+    memcpy(
+        to, from_begin,
+        CheckSub(get_uintptr(from_end), get_uintptr(from_begin)).ValueOrDie());
+  }
+
+  // Not trivially copyable, but movable: call the move constructor and
+  // destruct the original.
+  template <typename T2 = T,
+            typename std::enable_if<std::is_move_constructible<T2>::value &&
+                                        !base::is_trivially_copyable<T2>::value,
+                                    int>::type = 0>
+  static void MoveRange(T* from_begin, T* from_end, T* to) {
+    CHECK(!RangesOverlap(from_begin, from_end, to));
+    while (from_begin != from_end) {
+      new (to) T(std::move(*from_begin));
+      from_begin->~T();
+      from_begin++;
+      to++;
+    }
+  }
+
+  // Not movable, not trivially copyable: call the copy constructor and
+  // destruct the original.
+  template <typename T2 = T,
+            typename std::enable_if<!std::is_move_constructible<T2>::value &&
+                                        !base::is_trivially_copyable<T2>::value,
+                                    int>::type = 0>
+  static void MoveRange(T* from_begin, T* from_end, T* to) {
+    CHECK(!RangesOverlap(from_begin, from_end, to));
+    while (from_begin != from_end) {
+      new (to) T(*from_begin);
+      from_begin->~T();
+      from_begin++;
+      to++;
+    }
+  }
+
+ private:
+  static bool RangesOverlap(const T* from_begin,
+                            const T* from_end,
+                            const T* to) {
+    const auto from_begin_uintptr = get_uintptr(from_begin);
+    const auto from_end_uintptr = get_uintptr(from_end);
+    const auto to_uintptr = get_uintptr(to);
+    return !(
+        to >= from_end ||
+        CheckAdd(to_uintptr, CheckSub(from_end_uintptr, from_begin_uintptr))
+                .ValueOrDie() <= from_begin_uintptr);
+  }
+
+  T* buffer_ = nullptr;
+  size_t capacity_ = 0;
+
+  DISALLOW_COPY_AND_ASSIGN(VectorBuffer);
+};
+
+}  // namespace internal
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_VECTOR_BUFFERS_H_