From 666fc1266bccfd8e6eaaa084e7b42580bb8eb199 Mon Sep 17 00:00:00 2001
From: Abseil Team <absl-team@google.com>
Date: Thu, 4 Apr 2019 08:13:57 -0700
Subject: Export of internal Abseil changes. --
 bc89d3221e3927d08881d75eeee0e8db862300fa by Benjamin Barenblat
 <bbaren@google.com>:

Clean up C-style casts in `ABSL_ASSERT`

PiperOrigin-RevId: 241932756

--
17482daae4b3e2fc725b759586590ac466b72a1e by Jon Cohen <cohenjon@google.com>:

Move Gtest-specific CMake code to its own directory

PiperOrigin-RevId: 241920192

--
9ae52b4f665625352c0a789cff884bde492c28f5 by CJ Johnson <johnsoncj@google.com>:

Moves private data methods from InlinedVector to InlinedVector Storage in anticipation of migrating the Rep union type

PiperOrigin-RevId: 241794144

--
95315bc50a61a0aae4f171b44c2312158a43e72e by Jon Cohen <cohenjon@google.com>:

Use /DNOMINMAX in Abseil tests.  This offsets inlcudes of <windows.h> from gtest.

PiperOrigin-RevId: 241790584

--
ee505c7f2ab99d29c165ea21a07190474f64053d by CJ Johnson <johnsoncj@google.com>:

Adds inlined_vector_internal to the deps of inlined_vector in CMakeLists.txt

PiperOrigin-RevId: 241775332

--
94eb5165b49bab59ce7de143be38a4581d5658da by CJ Johnson <johnsoncj@google.com>:

Migrates InlinedVector Storage to class Metadata for compatibility with the eventual member-wise migration to the new exception safe implementation

PiperOrigin-RevId: 241633420

--
f99e172caad1ec8b35bf7bbabaf2833d55a6f055 by Abseil Team <absl-team@google.com>:

Add MSVC specific linker flags only to MSVC builds.

PiperOrigin-RevId: 241615711

--
3ad19d2779281e945bdf56643dc5cee3f730eb4f by Abseil Team <absl-team@google.com>:

Add a comment about per-process randomization of absl::Hash.

PiperOrigin-RevId: 241583697

--
8dfb02d725fee3528351b2da4ed32a7455f9858a by Tom Manshreck <shreck@google.com>:

Internal change

PiperOrigin-RevId: 241564734
GitOrigin-RevId: bc89d3221e3927d08881d75eeee0e8db862300fa
Change-Id: Ibad3da416d08a96ec1f8313f8b519b4270b7e01a
---
 absl/base/macros.h                       |   7 +-
 absl/container/BUILD.bazel               |   1 +
 absl/container/CMakeLists.txt            |   2 +
 absl/container/inlined_vector.h          | 354 ++++++++++++++---------------
 absl/container/internal/inlined_vector.h |  90 +++++---
 absl/copts/AbseilConfigureCopts.cmake    |   2 +-
 absl/copts/GENERATED_AbseilCopts.cmake   |   1 +
 absl/copts/GENERATED_copts.bzl           |   1 +
 absl/copts/copts.py                      |   1 +
 absl/hash/hash.h                         |   4 +
 absl/types/BUILD.bazel                   |   1 +
 absl/types/CMakeLists.txt                |   2 +
 absl/types/internal/optional.h           | 364 ++++++++++++++++++++++++++++++
 absl/types/optional.h                    | 375 ++-----------------------------
 14 files changed, 633 insertions(+), 572 deletions(-)
 create mode 100644 absl/types/internal/optional.h

(limited to 'absl')

diff --git a/absl/base/macros.h b/absl/base/macros.h
index 5b43d7c2bf3b..ca6207927e75 100644
--- a/absl/base/macros.h
+++ b/absl/base/macros.h
@@ -191,10 +191,11 @@ enum LinkerInitialized {
 // This macro is inspired by
 // https://akrzemi1.wordpress.com/2017/05/18/asserts-in-constexpr-functions/
 #if defined(NDEBUG)
-#define ABSL_ASSERT(expr) (false ? (void)(expr) : (void)0)
+#define ABSL_ASSERT(expr) \
+  (false ? static_cast<void>(expr) : static_cast<void>(0))
 #else
-#define ABSL_ASSERT(expr)              \
-  (ABSL_PREDICT_TRUE((expr)) ? (void)0 \
+#define ABSL_ASSERT(expr)                           \
+  (ABSL_PREDICT_TRUE((expr)) ? static_cast<void>(0) \
                              : [] { assert(false && #expr); }())  // NOLINT
 #endif
 
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 066a98862d5f..f25a9ff96b0b 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -123,6 +123,7 @@ cc_library(
     copts = ABSL_DEFAULT_COPTS,
     linkopts = ABSL_DEFAULT_LINKOPTS,
     deps = [
+        ":compressed_tuple",
         "//absl/meta:type_traits",
     ],
 )
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 292fea2a8383..3c44bd0ef160 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -115,6 +115,7 @@ absl_cc_library(
   COPTS
     ${ABSL_DEFAULT_COPTS}
   DEPS
+    absl::compressed_tuple
     absl::type_traits
   PUBLIC
 )
@@ -129,6 +130,7 @@ absl_cc_library(
   DEPS
     absl::algorithm
     absl::core_headers
+    absl::inlined_vector_internal
     absl::throw_delegate
     absl::memory
   PUBLIC
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 9b699b57a49a..c59fb9386e0b 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -70,8 +70,6 @@ class InlinedVector {
       N > 0, "InlinedVector cannot be instantiated with `0` inlined elements.");
 
   using Storage = inlined_vector_internal::Storage<InlinedVector>;
-  using Tag = typename Storage::Tag;
-  using AllocatorAndTag = typename Storage::AllocatorAndTag;
   using Allocation = typename Storage::Allocation;
 
   template <typename Iterator>
@@ -162,18 +160,19 @@ class InlinedVector {
 
   // Creates a copy of an `other` inlined vector using `other`'s allocator.
   InlinedVector(const InlinedVector& other)
-      : InlinedVector(other, other.allocator()) {}
+      : InlinedVector(other, other.storage_.GetAllocator()) {}
 
   // Creates a copy of an `other` inlined vector using a specified allocator.
   InlinedVector(const InlinedVector& other, const allocator_type& alloc)
       : storage_(alloc) {
     reserve(other.size());
-    if (allocated()) {
-      UninitializedCopy(other.begin(), other.end(), allocated_space());
-      tag().set_allocated_size(other.size());
+    if (storage_.GetIsAllocated()) {
+      UninitializedCopy(other.begin(), other.end(),
+                        storage_.GetAllocatedData());
+      storage_.SetAllocatedSize(other.size());
     } else {
-      UninitializedCopy(other.begin(), other.end(), inlined_space());
-      tag().set_inline_size(other.size());
+      UninitializedCopy(other.begin(), other.end(), storage_.GetInlinedData());
+      storage_.SetInlinedSize(other.size());
     }
   }
 
@@ -195,19 +194,20 @@ class InlinedVector {
   InlinedVector(InlinedVector&& other) noexcept(
       absl::allocator_is_nothrow<allocator_type>::value ||
       std::is_nothrow_move_constructible<value_type>::value)
-      : storage_(other.allocator()) {
-    if (other.allocated()) {
+      : storage_(other.storage_.GetAllocator()) {
+    if (other.storage_.GetIsAllocated()) {
       // We can just steal the underlying buffer from the source.
       // That leaves the source empty, so we clear its size.
-      init_allocation(other.allocation());
-      tag().set_allocated_size(other.size());
-      other.tag() = Tag();
+      storage_.InitAllocation(other.storage_.GetAllocation());
+      storage_.SetAllocatedSize(other.size());
+      other.storage_.SetInlinedSize(0);
     } else {
       UninitializedCopy(
-          std::make_move_iterator(other.inlined_space()),
-          std::make_move_iterator(other.inlined_space() + other.size()),
-          inlined_space());
-      tag().set_inline_size(other.size());
+          std::make_move_iterator(other.storage_.GetInlinedData()),
+          std::make_move_iterator(other.storage_.GetInlinedData() +
+                                  other.size()),
+          storage_.GetInlinedData());
+      storage_.SetInlinedSize(other.size());
     }
   }
 
@@ -227,26 +227,27 @@ class InlinedVector {
   InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
       absl::allocator_is_nothrow<allocator_type>::value)
       : storage_(alloc) {
-    if (other.allocated()) {
-      if (alloc == other.allocator()) {
+    if (other.storage_.GetIsAllocated()) {
+      if (alloc == other.storage_.GetAllocator()) {
         // We can just steal the allocation from the source.
-        tag() = other.tag();
-        init_allocation(other.allocation());
-        other.tag() = Tag();
+        storage_.SetAllocatedSize(other.size());
+        storage_.InitAllocation(other.storage_.GetAllocation());
+        other.storage_.SetInlinedSize(0);
       } else {
         // We need to use our own allocator
         reserve(other.size());
         UninitializedCopy(std::make_move_iterator(other.begin()),
                           std::make_move_iterator(other.end()),
-                          allocated_space());
-        tag().set_allocated_size(other.size());
+                          storage_.GetAllocatedData());
+        storage_.SetAllocatedSize(other.size());
       }
     } else {
       UninitializedCopy(
-          std::make_move_iterator(other.inlined_space()),
-          std::make_move_iterator(other.inlined_space() + other.size()),
-          inlined_space());
-      tag().set_inline_size(other.size());
+          std::make_move_iterator(other.storage_.GetInlinedData()),
+          std::make_move_iterator(other.storage_.GetInlinedData() +
+                                  other.size()),
+          storage_.GetInlinedData());
+      storage_.SetInlinedSize(other.size());
     }
   }
 
@@ -264,7 +265,7 @@ class InlinedVector {
   // `InlinedVector::size()`
   //
   // Returns the number of elements in the inlined vector.
-  size_type size() const noexcept { return tag().size(); }
+  size_type size() const noexcept { return storage_.GetSize(); }
 
   // `InlinedVector::max_size()`
   //
@@ -286,7 +287,8 @@ class InlinedVector {
   // will no longer be inlined and `capacity()` will equal its capacity on the
   // allocated heap.
   size_type capacity() const noexcept {
-    return allocated() ? allocation().capacity() : static_cast<size_type>(N);
+    return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity()
+                                     : static_cast<size_type>(N);
   }
 
   // `InlinedVector::data()`
@@ -295,14 +297,16 @@ class InlinedVector {
   // used to access and modify the contained elements.
   // Only results within the range [`0`, `size()`) are defined.
   pointer data() noexcept {
-    return allocated() ? allocated_space() : inlined_space();
+    return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
+                                     : storage_.GetInlinedData();
   }
 
   // Overload of `InlinedVector::data()` to return a `const_pointer` to elements
   // of the inlined vector. This pointer can be used to access (but not modify)
   // the contained elements.
   const_pointer data() const noexcept {
-    return allocated() ? allocated_space() : inlined_space();
+    return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
+                                     : storage_.GetInlinedData();
   }
 
   // `InlinedVector::operator[]()`
@@ -436,7 +440,7 @@ class InlinedVector {
   // `InlinedVector::get_allocator()`
   //
   // Returns a copy of the allocator of the inlined vector.
-  allocator_type get_allocator() const { return allocator(); }
+  allocator_type get_allocator() const { return storage_.GetAllocator(); }
 
   // ---------------------------------------------------------------------------
   // InlinedVector Member Mutators
@@ -477,13 +481,13 @@ class InlinedVector {
   InlinedVector& operator=(InlinedVector&& other) {
     if (ABSL_PREDICT_FALSE(this == std::addressof(other))) return *this;
 
-    if (other.allocated()) {
+    if (other.storage_.GetIsAllocated()) {
       clear();
-      tag().set_allocated_size(other.size());
-      init_allocation(other.allocation());
-      other.tag() = Tag();
+      storage_.SetAllocatedSize(other.size());
+      storage_.InitAllocation(other.storage_.GetAllocation());
+      other.storage_.SetInlinedSize(0);
     } else {
-      if (allocated()) clear();
+      if (storage_.GetIsAllocated()) clear();
       // Both are inlined now.
       if (size() < other.size()) {
         auto mid = std::make_move_iterator(other.begin() + size());
@@ -494,7 +498,7 @@ class InlinedVector {
                                  std::make_move_iterator(other.end()), begin());
         Destroy(new_end, end());
       }
-      tag().set_inline_size(other.size());
+      storage_.SetInlinedSize(other.size());
     }
     return *this;
   }
@@ -511,12 +515,14 @@ class InlinedVector {
     // Grow
     reserve(n);
     std::fill_n(begin(), size(), v);
-    if (allocated()) {
-      UninitializedFill(allocated_space() + size(), allocated_space() + n, v);
-      tag().set_allocated_size(n);
+    if (storage_.GetIsAllocated()) {
+      UninitializedFill(storage_.GetAllocatedData() + size(),
+                        storage_.GetAllocatedData() + n, v);
+      storage_.SetAllocatedSize(n);
     } else {
-      UninitializedFill(inlined_space() + size(), inlined_space() + n, v);
-      tag().set_inline_size(n);
+      UninitializedFill(storage_.GetInlinedData() + size(),
+                        storage_.GetInlinedData() + n, v);
+      storage_.SetInlinedSize(n);
     }
   }
 
@@ -564,12 +570,14 @@ class InlinedVector {
     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);
+    if (storage_.GetIsAllocated()) {
+      UninitializedFill(storage_.GetAllocatedData() + s,
+                        storage_.GetAllocatedData() + n);
+      storage_.SetAllocatedSize(n);
     } else {
-      UninitializedFill(inlined_space() + s, inlined_space() + n);
-      tag().set_inline_size(n);
+      UninitializedFill(storage_.GetInlinedData() + s,
+                        storage_.GetInlinedData() + n);
+      storage_.SetInlinedSize(n);
     }
   }
 
@@ -586,12 +594,14 @@ class InlinedVector {
     assert(capacity() >= n);
 
     // Fill new space with copies of `v`.
-    if (allocated()) {
-      UninitializedFill(allocated_space() + s, allocated_space() + n, v);
-      tag().set_allocated_size(n);
+    if (storage_.GetIsAllocated()) {
+      UninitializedFill(storage_.GetAllocatedData() + s,
+                        storage_.GetAllocatedData() + n, v);
+      storage_.SetAllocatedSize(n);
     } else {
-      UninitializedFill(inlined_space() + s, inlined_space() + n, v);
-      tag().set_inline_size(n);
+      UninitializedFill(storage_.GetInlinedData() + s,
+                        storage_.GetInlinedData() + n, v);
+      storage_.SetInlinedSize(n);
     }
   }
 
@@ -688,12 +698,12 @@ class InlinedVector {
       return GrowAndEmplaceBack(std::forward<Args>(args)...);
     }
     pointer space;
-    if (allocated()) {
-      tag().set_allocated_size(s + 1);
-      space = allocated_space();
+    if (storage_.GetIsAllocated()) {
+      storage_.SetAllocatedSize(s + 1);
+      space = storage_.GetAllocatedData();
     } else {
-      tag().set_inline_size(s + 1);
-      space = inlined_space();
+      storage_.SetInlinedSize(s + 1);
+      space = storage_.GetInlinedData();
     }
     return Construct(space + s, std::forward<Args>(args)...);
   }
@@ -716,12 +726,13 @@ class InlinedVector {
   void pop_back() noexcept {
     assert(!empty());
     size_type s = size();
-    if (allocated()) {
-      Destroy(allocated_space() + s - 1, allocated_space() + s);
-      tag().set_allocated_size(s - 1);
+    if (storage_.GetIsAllocated()) {
+      Destroy(storage_.GetAllocatedData() + s - 1,
+              storage_.GetAllocatedData() + s);
+      storage_.SetAllocatedSize(s - 1);
     } else {
-      Destroy(inlined_space() + s - 1, inlined_space() + s);
-      tag().set_inline_size(s - 1);
+      Destroy(storage_.GetInlinedData() + s - 1, storage_.GetInlinedData() + s);
+      storage_.SetInlinedSize(s - 1);
     }
   }
 
@@ -757,12 +768,12 @@ class InlinedVector {
     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);
+      if (storage_.GetIsAllocated()) {
+        space = storage_.GetAllocatedData();
+        storage_.SetAllocatedSize(s - erase_gap);
       } else {
-        space = inlined_space();
-        tag().set_inline_size(s - erase_gap);
+        space = storage_.GetInlinedData();
+        storage_.SetInlinedSize(s - erase_gap);
       }
       std::move(range_end, space + s, range_start);
       Destroy(space + s - erase_gap, space + s);
@@ -776,13 +787,13 @@ class InlinedVector {
   // deallocates the heap allocation if the inlined vector was allocated.
   void clear() noexcept {
     size_type s = size();
-    if (allocated()) {
-      Destroy(allocated_space(), allocated_space() + s);
-      allocation().Dealloc(allocator());
+    if (storage_.GetIsAllocated()) {
+      Destroy(storage_.GetAllocatedData(), storage_.GetAllocatedData() + s);
+      storage_.GetAllocation().Dealloc(storage_.GetAllocator());
     } else if (s != 0) {  // do nothing for empty vectors
-      Destroy(inlined_space(), inlined_space() + s);
+      Destroy(storage_.GetInlinedData(), storage_.GetInlinedData() + s);
     }
-    tag() = Tag();
+    storage_.SetInlinedSize(0);
   }
 
   // `InlinedVector::reserve()`
@@ -814,7 +825,8 @@ class InlinedVector {
   // smaller heap allocation.
   void shrink_to_fit() {
     const auto s = size();
-    if (ABSL_PREDICT_FALSE(!allocated() || s == capacity())) return;
+    if (ABSL_PREDICT_FALSE(!storage_.GetIsAllocated() || s == capacity()))
+      return;
 
     if (s <= N) {
       // Move the elements to the inlined storage.
@@ -829,9 +841,9 @@ class InlinedVector {
     // Reallocate storage and move elements.
     // We can't simply use the same approach as above, because `assign()` would
     // call into `reserve()` internally and reserve larger capacity than we need
-    Allocation new_allocation(allocator(), s);
-    UninitializedCopy(std::make_move_iterator(allocated_space()),
-                      std::make_move_iterator(allocated_space() + s),
+    Allocation new_allocation(storage_.GetAllocator(), s);
+    UninitializedCopy(std::make_move_iterator(storage_.GetAllocatedData()),
+                      std::make_move_iterator(storage_.GetAllocatedData() + s),
                       new_allocation.buffer());
     ResetAllocation(new_allocation, s);
   }
@@ -849,67 +861,24 @@ class InlinedVector {
   template <typename H, typename TheT, size_t TheN, typename TheA>
   friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a);
 
-  const Tag& tag() const { return storage_.allocator_and_tag_.tag(); }
-
-  Tag& tag() { return storage_.allocator_and_tag_.tag(); }
-
-  Allocation& allocation() {
-    return reinterpret_cast<Allocation&>(
-        storage_.rep_.allocation_storage.allocation);
-  }
-
-  const Allocation& allocation() const {
-    return reinterpret_cast<const Allocation&>(
-        storage_.rep_.allocation_storage.allocation);
-  }
-
-  void init_allocation(const Allocation& allocation) {
-    new (static_cast<void*>(std::addressof(
-        storage_.rep_.allocation_storage.allocation))) Allocation(allocation);
-  }
-
-  // TODO(absl-team): investigate whether the reinterpret_cast is appropriate.
-  pointer inlined_space() {
-    return reinterpret_cast<pointer>(
-        std::addressof(storage_.rep_.inlined_storage.inlined[0]));
-  }
-
-  const_pointer inlined_space() const {
-    return reinterpret_cast<const_pointer>(
-        std::addressof(storage_.rep_.inlined_storage.inlined[0]));
-  }
-
-  pointer allocated_space() { return allocation().buffer(); }
-
-  const_pointer allocated_space() const { return allocation().buffer(); }
-
-  const allocator_type& allocator() const {
-    return storage_.allocator_and_tag_.allocator();
-  }
-
-  allocator_type& allocator() {
-    return storage_.allocator_and_tag_.allocator();
-  }
-
-  bool allocated() const { return tag().allocated(); }
-
   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;
+    if (storage_.GetIsAllocated()) {
+      Destroy(storage_.GetAllocatedData(),
+              storage_.GetAllocatedData() + size());
+      assert(begin() == storage_.GetAllocatedData());
+      storage_.GetAllocation().Dealloc(storage_.GetAllocator());
+      storage_.GetAllocation() = new_allocation;
     } else {
-      Destroy(inlined_space(), inlined_space() + size());
-      init_allocation(new_allocation);  // bug: only init once
+      Destroy(storage_.GetInlinedData(), storage_.GetInlinedData() + size());
+      storage_.InitAllocation(new_allocation);  // bug: only init once
     }
-    tag().set_allocated_size(new_size);
+    storage_.SetAllocatedSize(new_size);
   }
 
   template <typename... Args>
   reference Construct(pointer p, Args&&... args) {
     std::allocator_traits<allocator_type>::construct(
-        allocator(), p, std::forward<Args>(args)...);
+        storage_.GetAllocator(), p, std::forward<Args>(args)...);
     return *p;
   }
 
@@ -926,7 +895,8 @@ class InlinedVector {
   // Destroy [`from`, `to`) in place.
   void Destroy(pointer from, pointer to) {
     for (pointer cur = from; cur != to; ++cur) {
-      std::allocator_traits<allocator_type>::destroy(allocator(), cur);
+      std::allocator_traits<allocator_type>::destroy(storage_.GetAllocator(),
+                                                     cur);
     }
 #if !defined(NDEBUG)
     // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
@@ -946,7 +916,7 @@ class InlinedVector {
     const size_type s = size();
     assert(s <= capacity());
 
-    size_type target = (std::max)(N, s + delta);
+    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?
@@ -955,7 +925,7 @@ class InlinedVector {
       new_capacity <<= 1;
     }
 
-    Allocation new_allocation(allocator(), new_capacity);
+    Allocation new_allocation(storage_.GetAllocator(), new_capacity);
 
     UninitializedCopy(std::make_move_iterator(data()),
                       std::make_move_iterator(data() + s),
@@ -987,7 +957,7 @@ class InlinedVector {
       }
       // Move everyone into the new allocation, leaving a gap of `n` for the
       // requested shift.
-      Allocation new_allocation(allocator(), new_capacity);
+      Allocation new_allocation(storage_.GetAllocator(), new_capacity);
       size_type index = position - begin();
       UninitializedCopy(std::make_move_iterator(data()),
                         std::make_move_iterator(data() + index),
@@ -1026,7 +996,7 @@ class InlinedVector {
       start_used = pos;
       start_raw = pos + new_elements_in_used_space;
     }
-    tag().add_size(n);
+    storage_.AddSize(n);
     return std::make_pair(start_used, start_raw);
   }
 
@@ -1035,7 +1005,7 @@ class InlinedVector {
     assert(size() == capacity());
     const size_type s = size();
 
-    Allocation new_allocation(allocator(), 2 * capacity());
+    Allocation new_allocation(storage_.GetAllocator(), 2 * capacity());
 
     reference new_element =
         Construct(new_allocation.buffer() + s, std::forward<Args>(args)...);
@@ -1049,26 +1019,30 @@ class InlinedVector {
   }
 
   void InitAssign(size_type n) {
-    if (n > N) {
-      Allocation new_allocation(allocator(), n);
-      init_allocation(new_allocation);
-      UninitializedFill(allocated_space(), allocated_space() + n);
-      tag().set_allocated_size(n);
+    if (n > static_cast<size_type>(N)) {
+      Allocation new_allocation(storage_.GetAllocator(), n);
+      storage_.InitAllocation(new_allocation);
+      UninitializedFill(storage_.GetAllocatedData(),
+                        storage_.GetAllocatedData() + n);
+      storage_.SetAllocatedSize(n);
     } else {
-      UninitializedFill(inlined_space(), inlined_space() + n);
-      tag().set_inline_size(n);
+      UninitializedFill(storage_.GetInlinedData(),
+                        storage_.GetInlinedData() + n);
+      storage_.SetInlinedSize(n);
     }
   }
 
   void InitAssign(size_type n, const_reference v) {
-    if (n > N) {
-      Allocation new_allocation(allocator(), n);
-      init_allocation(new_allocation);
-      UninitializedFill(allocated_space(), allocated_space() + n, v);
-      tag().set_allocated_size(n);
+    if (n > static_cast<size_type>(N)) {
+      Allocation new_allocation(storage_.GetAllocator(), n);
+      storage_.InitAllocation(new_allocation);
+      UninitializedFill(storage_.GetAllocatedData(),
+                        storage_.GetAllocatedData() + n, v);
+      storage_.SetAllocatedSize(n);
     } else {
-      UninitializedFill(inlined_space(), inlined_space() + n, v);
-      tag().set_inline_size(n);
+      UninitializedFill(storage_.GetInlinedData(),
+                        storage_.GetInlinedData() + n, v);
+      storage_.SetInlinedSize(n);
     }
   }
 
@@ -1087,12 +1061,12 @@ class InlinedVector {
     reserve(length);
     iterator out = begin();
     for (; out != end(); ++first, ++out) *out = *first;
-    if (allocated()) {
+    if (storage_.GetIsAllocated()) {
       UninitializedCopy(first, last, out);
-      tag().set_allocated_size(length);
+      storage_.SetAllocatedSize(length);
     } else {
       UninitializedCopy(first, last, out);
-      tag().set_inline_size(length);
+      storage_.SetInlinedSize(length);
     }
   }
 
@@ -1102,12 +1076,12 @@ class InlinedVector {
 
     auto length = std::distance(first, last);
     reserve(size() + length);
-    if (allocated()) {
-      UninitializedCopy(first, last, allocated_space() + size());
-      tag().set_allocated_size(size() + length);
+    if (storage_.GetIsAllocated()) {
+      UninitializedCopy(first, last, storage_.GetAllocatedData() + size());
+      storage_.SetAllocatedSize(size() + length);
     } else {
-      UninitializedCopy(first, last, inlined_space() + size());
-      tag().set_inline_size(size() + length);
+      UninitializedCopy(first, last, storage_.GetInlinedData() + size());
+      storage_.SetInlinedSize(size() + length);
     }
   }
 
@@ -1145,14 +1119,19 @@ class InlinedVector {
   void SwapImpl(InlinedVector& other) {
     using std::swap;  // Augment ADL with `std::swap`.
 
-    if (allocated() && other.allocated()) {
+    bool is_allocated = storage_.GetIsAllocated();
+    bool other_is_allocated = other.storage_.GetIsAllocated();
+
+    if (is_allocated && other_is_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());
+      storage_.SwapSizeAndIsAllocated(other.storage_);
+      swap(storage_.GetAllocation(), other.storage_.GetAllocation());
+      swap(storage_.GetAllocator(), other.storage_.GetAllocator());
+
       return;
     }
-    if (!allocated() && !other.allocated()) {
+
+    if (!is_allocated && !other_is_allocated) {
       // Both inlined: swap up to smaller size, then move remaining elements.
       InlinedVector* a = this;
       InlinedVector* b = std::addressof(other);
@@ -1164,18 +1143,21 @@ class InlinedVector {
       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());
+      std::swap_ranges(a->storage_.GetInlinedData(),
+                       a->storage_.GetInlinedData() + b_size,
+                       b->storage_.GetInlinedData());
 
       // Move the remaining elements:
       //   [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b`
-      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);
+      b->UninitializedCopy(a->storage_.GetInlinedData() + b_size,
+                           a->storage_.GetInlinedData() + a_size,
+                           b->storage_.GetInlinedData() + b_size);
+      a->Destroy(a->storage_.GetInlinedData() + b_size,
+                 a->storage_.GetInlinedData() + a_size);
+
+      storage_.SwapSizeAndIsAllocated(other.storage_);
+      swap(storage_.GetAllocator(), other.storage_.GetAllocator());
 
-      swap(a->tag(), b->tag());
-      swap(a->allocator(), b->allocator());
       assert(b->size() == a_size);
       assert(a->size() == b_size);
       return;
@@ -1188,31 +1170,35 @@ class InlinedVector {
     // the tags.
     InlinedVector* a = this;
     InlinedVector* b = std::addressof(other);
-    if (a->allocated()) {
+    if (a->storage_.GetIsAllocated()) {
       swap(a, b);
     }
-    assert(!a->allocated());
-    assert(b->allocated());
+
+    assert(!a->storage_.GetIsAllocated());
+    assert(b->storage_.GetIsAllocated());
+
     const size_type a_size = a->size();
     const size_type b_size = b->size();
     // In an optimized build, `b_size` would be unused.
     static_cast<void>(b_size);
 
-    // Made Local copies of `size()`, don't need `tag()` accurate anymore
-    swap(a->tag(), b->tag());
+    // Made Local copies of `size()`, these can now be swapped
+    a->storage_.SwapSizeAndIsAllocated(b->storage_);
 
     // Copy `b_allocation` out before `b`'s union gets clobbered by
     // `inline_space`
-    Allocation b_allocation = b->allocation();
+    Allocation b_allocation = b->storage_.GetAllocation();
 
-    b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
-                         b->inlined_space());
-    a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
+    b->UninitializedCopy(a->storage_.GetInlinedData(),
+                         a->storage_.GetInlinedData() + a_size,
+                         b->storage_.GetInlinedData());
+    a->Destroy(a->storage_.GetInlinedData(),
+               a->storage_.GetInlinedData() + a_size);
 
-    a->allocation() = b_allocation;
+    a->storage_.GetAllocation() = b_allocation;
 
-    if (a->allocator() != b->allocator()) {
-      swap(a->allocator(), b->allocator());
+    if (a->storage_.GetAllocator() != b->storage_.GetAllocator()) {
+      swap(a->storage_.GetAllocator(), b->storage_.GetAllocator());
     }
 
     assert(b->size() == a_size);
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index 24059d94c876..7aa05b6a9974 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -18,7 +18,9 @@
 #include <cstddef>
 #include <iterator>
 #include <memory>
+#include <utility>
 
+#include "absl/container/internal/compressed_tuple.h"
 #include "absl/meta/type_traits.h"
 
 namespace absl {
@@ -31,6 +33,8 @@ template <template <typename, size_t, typename> class InlinedVector, typename T,
           size_t N, typename A>
 class Storage<InlinedVector<T, N, A>> {
  public:
+  class Allocation;  // TODO(johnsoncj): Remove after migration
+
   using allocator_type = A;
   using value_type = typename allocator_type::value_type;
   using pointer = typename allocator_type::pointer;
@@ -45,38 +49,63 @@ class Storage<InlinedVector<T, N, A>> {
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
-  explicit Storage(const allocator_type& a) : allocator_and_tag_(a) {}
+  explicit Storage(const allocator_type& alloc)
+      : metadata_(alloc, /* empty and inlined */ 0) {}
 
-  // TODO(johnsoncj): Make the below types and members private after migration
+  size_type GetSize() const { return GetSizeAndIsAllocated() >> 1; }
 
-  // Holds whether the vector is allocated or not in the lowest bit and the size
-  // in the high bits:
-  //   `size_ = (size << 1) | is_allocated;`
-  class Tag {
-    size_type size_;
+  bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; }
 
-   public:
-    Tag() : size_(0) {}
-    size_type size() const { return size_ / 2; }
-    void add_size(size_type n) { size_ += n * 2; }
-    void set_inline_size(size_type n) { size_ = n * 2; }
-    void set_allocated_size(size_type n) { size_ = (n * 2) + 1; }
-    bool allocated() const { return size_ % 2; }
-  };
+  Allocation& GetAllocation() {
+    return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation);
+  }
 
-  // Derives from `allocator_type` to use the empty base class optimization.
-  // If the `allocator_type` is stateless, we can store our instance for free.
-  class AllocatorAndTag : private allocator_type {
-    Tag tag_;
+  const Allocation& GetAllocation() const {
+    return reinterpret_cast<const Allocation&>(
+        rep_.allocation_storage.allocation);
+  }
 
-   public:
-    explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {}
-    Tag& tag() { return tag_; }
-    const Tag& tag() const { return tag_; }
-    allocator_type& allocator() { return *this; }
-    const allocator_type& allocator() const { return *this; }
-  };
+  pointer GetInlinedData() {
+    return reinterpret_cast<pointer>(
+        std::addressof(rep_.inlined_storage.inlined[0]));
+  }
+
+  const_pointer GetInlinedData() const {
+    return reinterpret_cast<const_pointer>(
+        std::addressof(rep_.inlined_storage.inlined[0]));
+  }
+
+  pointer GetAllocatedData() { return GetAllocation().buffer(); }
+
+  const_pointer GetAllocatedData() const { return GetAllocation().buffer(); }
+
+  size_type GetAllocatedCapacity() const { return GetAllocation().capacity(); }
 
+  allocator_type& GetAllocator() { return metadata_.template get<0>(); }
+
+  const allocator_type& GetAllocator() const {
+    return metadata_.template get<0>();
+  }
+
+  void SetAllocatedSize(size_type size) {
+    GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1);
+  }
+
+  void SetInlinedSize(size_type size) { GetSizeAndIsAllocated() = size << 1; }
+
+  void AddSize(size_type count) { GetSizeAndIsAllocated() += count << 1; }
+
+  void InitAllocation(const Allocation& allocation) {
+    new (static_cast<void*>(std::addressof(rep_.allocation_storage.allocation)))
+        Allocation(allocation);
+  }
+
+  void SwapSizeAndIsAllocated(Storage& other) {
+    using std::swap;
+    swap(GetSizeAndIsAllocated(), other.GetSizeAndIsAllocated());
+  }
+
+  // TODO(johnsoncj): Make the below types private after migration
   class Allocation {
     size_type capacity_;
     pointer buffer_;
@@ -95,6 +124,13 @@ class Storage<InlinedVector<T, N, A>> {
     }
   };
 
+ private:
+  size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
+
+  const size_type& GetSizeAndIsAllocated() const {
+    return metadata_.template get<1>();
+  }
+
   // Stores either the inlined or allocated representation
   union Rep {
     using ValueTypeBuffer =
@@ -116,7 +152,7 @@ class Storage<InlinedVector<T, N, A>> {
     AllocatedRep allocation_storage;
   };
 
-  AllocatorAndTag allocator_and_tag_;
+  container_internal::CompressedTuple<allocator_type, size_type> metadata_;
   Rep rep_;
 };
 
diff --git a/absl/copts/AbseilConfigureCopts.cmake b/absl/copts/AbseilConfigureCopts.cmake
index ae29d9e9a045..eaef30b0e591 100644
--- a/absl/copts/AbseilConfigureCopts.cmake
+++ b/absl/copts/AbseilConfigureCopts.cmake
@@ -16,11 +16,11 @@ elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang")
     set(ABSL_DEFAULT_COPTS "${ABSL_CLANG_CL_FLAGS}")
     set(ABSL_TEST_COPTS "${ABSL_CLANG_CL_FLAGS};${ABSL_CLANG_CL_TEST_FLAGS}")
     set(ABSL_EXCEPTIONS_FLAG "${ABSL_CLANG_CL_EXCEPTIONS_FLAGS}")
+    set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}")
   else()
     set(ABSL_DEFAULT_COPTS "${ABSL_LLVM_FLAGS}")
     set(ABSL_TEST_COPTS "${ABSL_LLVM_FLAGS};${ABSL_LLVM_TEST_FLAGS}")
     set(ABSL_EXCEPTIONS_FLAG "${ABSL_LLVM_EXCEPTIONS_FLAGS}")
-    set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}")
     if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang")
       # AppleClang doesn't have lsan
       # https://developer.apple.com/documentation/code_diagnostics
diff --git a/absl/copts/GENERATED_AbseilCopts.cmake b/absl/copts/GENERATED_AbseilCopts.cmake
index 16cf9feaee8e..cf38ec1247cf 100644
--- a/absl/copts/GENERATED_AbseilCopts.cmake
+++ b/absl/copts/GENERATED_AbseilCopts.cmake
@@ -211,4 +211,5 @@ list(APPEND ABSL_MSVC_TEST_FLAGS
     "/wd4018"
     "/wd4101"
     "/wd4503"
+    "/DNOMINMAX"
 )
diff --git a/absl/copts/GENERATED_copts.bzl b/absl/copts/GENERATED_copts.bzl
index 0669c7242e72..52e1a949f2d3 100644
--- a/absl/copts/GENERATED_copts.bzl
+++ b/absl/copts/GENERATED_copts.bzl
@@ -212,4 +212,5 @@ ABSL_MSVC_TEST_FLAGS = [
     "/wd4018",
     "/wd4101",
     "/wd4503",
+    "/DNOMINMAX",
 ]
diff --git a/absl/copts/copts.py b/absl/copts/copts.py
index cd56890671e5..880ff991bda4 100644
--- a/absl/copts/copts.py
+++ b/absl/copts/copts.py
@@ -183,6 +183,7 @@ COPT_VARS = {
         "/wd4018",  # signed/unsigned mismatch
         "/wd4101",  # unreferenced local variable
         "/wd4503",  # decorated name length exceeded, name was truncated
+        "/DNOMINMAX",  # disable the min() and max() macros from <windows.h>
     ],
     "ABSL_MSVC_EXCEPTIONS_FLAGS":
         MSVC_STYLE_EXCEPTIONS_FLAGS,
diff --git a/absl/hash/hash.h b/absl/hash/hash.h
index c0ede35ad523..339b685ffd20 100644
--- a/absl/hash/hash.h
+++ b/absl/hash/hash.h
@@ -36,6 +36,10 @@
 // framework by simply combining its state with the state of known, hashable
 // types. Hashing of that combined state is separately done by `absl::Hash`.
 //
+// One should assume that a hash algorithm is chosen randomly at the start of
+// each process.  E.g., absl::Hash<int>()(9) in one process and
+// absl::Hash<int>()(9) in another process are likely to differ.
+//
 // Example:
 //
 //   // Suppose we have a class `Circle` for which we want to add hashing
diff --git a/absl/types/BUILD.bazel b/absl/types/BUILD.bazel
index feac34b1c9f9..a25487184bc1 100644
--- a/absl/types/BUILD.bazel
+++ b/absl/types/BUILD.bazel
@@ -173,6 +173,7 @@ cc_test(
 
 cc_library(
     name = "optional",
+    srcs = ["internal/optional.h"],
     hdrs = ["optional.h"],
     copts = ABSL_DEFAULT_COPTS,
     linkopts = ABSL_DEFAULT_LINKOPTS,
diff --git a/absl/types/CMakeLists.txt b/absl/types/CMakeLists.txt
index 56f9fffd6f92..9da94eb56120 100644
--- a/absl/types/CMakeLists.txt
+++ b/absl/types/CMakeLists.txt
@@ -174,6 +174,8 @@ absl_cc_library(
     optional
   HDRS
     "optional.h"
+  SRCS
+    "internal/optional.h"
   COPTS
     ${ABSL_DEFAULT_COPTS}
   DEPS
diff --git a/absl/types/internal/optional.h b/absl/types/internal/optional.h
new file mode 100644
index 000000000000..562c84ef5af7
--- /dev/null
+++ b/absl/types/internal/optional.h
@@ -0,0 +1,364 @@
+// 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
+//
+//      https://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_TYPES_INTERNAL_OPTIONAL_H_
+#define ABSL_TYPES_INTERNAL_OPTIONAL_H_
+
+#include <functional>
+#include <new>
+#include <type_traits>
+#include <utility>
+
+#include "absl/base/internal/inline_variable.h"
+#include "absl/memory/memory.h"
+#include "absl/meta/type_traits.h"
+#include "absl/utility/utility.h"
+
+namespace absl {
+
+// Forward declaration
+template <typename T>
+class optional;
+
+namespace optional_internal {
+
+// This tag type is used as a constructor parameter type for `nullopt_t`.
+struct init_t {
+  explicit init_t() = default;
+};
+
+struct empty_struct {};
+
+// This class stores the data in optional<T>.
+// It is specialized based on whether T is trivially destructible.
+// This is the specialization for non trivially destructible type.
+template <typename T, bool unused = std::is_trivially_destructible<T>::value>
+class optional_data_dtor_base {
+  struct dummy_type {
+    static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
+    // Use an array to avoid GCC 6 placement-new warning.
+    empty_struct data[sizeof(T) / sizeof(empty_struct)];
+  };
+
+ protected:
+  // Whether there is data or not.
+  bool engaged_;
+  // Data storage
+  union {
+    dummy_type dummy_;
+    T data_;
+  };
+
+  void destruct() noexcept {
+    if (engaged_) {
+      data_.~T();
+      engaged_ = false;
+    }
+  }
+
+  // dummy_ must be initialized for constexpr constructor.
+  constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
+
+  template <typename... Args>
+  constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
+      : engaged_(true), data_(absl::forward<Args>(args)...) {}
+
+  ~optional_data_dtor_base() { destruct(); }
+};
+
+// Specialization for trivially destructible type.
+template <typename T>
+class optional_data_dtor_base<T, true> {
+  struct dummy_type {
+    static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
+    // Use array to avoid GCC 6 placement-new warning.
+    empty_struct data[sizeof(T) / sizeof(empty_struct)];
+  };
+
+ protected:
+  // Whether there is data or not.
+  bool engaged_;
+  // Data storage
+  union {
+    dummy_type dummy_;
+    T data_;
+  };
+  void destruct() noexcept { engaged_ = false; }
+
+  // dummy_ must be initialized for constexpr constructor.
+  constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
+
+  template <typename... Args>
+  constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
+      : engaged_(true), data_(absl::forward<Args>(args)...) {}
+};
+
+template <typename T>
+class optional_data_base : public optional_data_dtor_base<T> {
+ protected:
+  using base = optional_data_dtor_base<T>;
+#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
+  using base::base;
+#else
+  optional_data_base() = default;
+
+  template <typename... Args>
+  constexpr explicit optional_data_base(in_place_t t, Args&&... args)
+      : base(t, absl::forward<Args>(args)...) {}
+#endif
+
+  template <typename... Args>
+  void construct(Args&&... args) {
+    // Use dummy_'s address to work around casting cv-qualified T* to void*.
+    ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...);
+    this->engaged_ = true;
+  }
+
+  template <typename U>
+  void assign(U&& u) {
+    if (this->engaged_) {
+      this->data_ = std::forward<U>(u);
+    } else {
+      construct(std::forward<U>(u));
+    }
+  }
+};
+
+// TODO(absl-team): Add another class using
+// std::is_trivially_move_constructible trait when available to match
+// http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that
+// have trivial move but nontrivial copy.
+// Also, we should be checking is_trivially_copyable here, which is not
+// supported now, so we use is_trivially_* traits instead.
+template <typename T,
+          bool unused = absl::is_trivially_copy_constructible<T>::value&&
+              absl::is_trivially_copy_assignable<typename std::remove_cv<
+                  T>::type>::value&& std::is_trivially_destructible<T>::value>
+class optional_data;
+
+// Trivially copyable types
+template <typename T>
+class optional_data<T, true> : public optional_data_base<T> {
+ protected:
+#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
+  using optional_data_base<T>::optional_data_base;
+#else
+  optional_data() = default;
+
+  template <typename... Args>
+  constexpr explicit optional_data(in_place_t t, Args&&... args)
+      : optional_data_base<T>(t, absl::forward<Args>(args)...) {}
+#endif
+};
+
+template <typename T>
+class optional_data<T, false> : public optional_data_base<T> {
+ protected:
+#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
+  using optional_data_base<T>::optional_data_base;
+#else
+  template <typename... Args>
+  constexpr explicit optional_data(in_place_t t, Args&&... args)
+      : optional_data_base<T>(t, absl::forward<Args>(args)...) {}
+#endif
+
+  optional_data() = default;
+
+  optional_data(const optional_data& rhs) : optional_data_base<T>() {
+    if (rhs.engaged_) {
+      this->construct(rhs.data_);
+    }
+  }
+
+  optional_data(optional_data&& rhs) noexcept(
+      absl::default_allocator_is_nothrow::value ||
+      std::is_nothrow_move_constructible<T>::value)
+      : optional_data_base<T>() {
+    if (rhs.engaged_) {
+      this->construct(std::move(rhs.data_));
+    }
+  }
+
+  optional_data& operator=(const optional_data& rhs) {
+    if (rhs.engaged_) {
+      this->assign(rhs.data_);
+    } else {
+      this->destruct();
+    }
+    return *this;
+  }
+
+  optional_data& operator=(optional_data&& rhs) noexcept(
+      std::is_nothrow_move_assignable<T>::value&&
+          std::is_nothrow_move_constructible<T>::value) {
+    if (rhs.engaged_) {
+      this->assign(std::move(rhs.data_));
+    } else {
+      this->destruct();
+    }
+    return *this;
+  }
+};
+
+// Ordered by level of restriction, from low to high.
+// Copyable implies movable.
+enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 };
+
+// Base class for enabling/disabling copy/move constructor.
+template <copy_traits>
+class optional_ctor_base;
+
+template <>
+class optional_ctor_base<copy_traits::copyable> {
+ public:
+  constexpr optional_ctor_base() = default;
+  optional_ctor_base(const optional_ctor_base&) = default;
+  optional_ctor_base(optional_ctor_base&&) = default;
+  optional_ctor_base& operator=(const optional_ctor_base&) = default;
+  optional_ctor_base& operator=(optional_ctor_base&&) = default;
+};
+
+template <>
+class optional_ctor_base<copy_traits::movable> {
+ public:
+  constexpr optional_ctor_base() = default;
+  optional_ctor_base(const optional_ctor_base&) = delete;
+  optional_ctor_base(optional_ctor_base&&) = default;
+  optional_ctor_base& operator=(const optional_ctor_base&) = default;
+  optional_ctor_base& operator=(optional_ctor_base&&) = default;
+};
+
+template <>
+class optional_ctor_base<copy_traits::non_movable> {
+ public:
+  constexpr optional_ctor_base() = default;
+  optional_ctor_base(const optional_ctor_base&) = delete;
+  optional_ctor_base(optional_ctor_base&&) = delete;
+  optional_ctor_base& operator=(const optional_ctor_base&) = default;
+  optional_ctor_base& operator=(optional_ctor_base&&) = default;
+};
+
+// Base class for enabling/disabling copy/move assignment.
+template <copy_traits>
+class optional_assign_base;
+
+template <>
+class optional_assign_base<copy_traits::copyable> {
+ public:
+  constexpr optional_assign_base() = default;
+  optional_assign_base(const optional_assign_base&) = default;
+  optional_assign_base(optional_assign_base&&) = default;
+  optional_assign_base& operator=(const optional_assign_base&) = default;
+  optional_assign_base& operator=(optional_assign_base&&) = default;
+};
+
+template <>
+class optional_assign_base<copy_traits::movable> {
+ public:
+  constexpr optional_assign_base() = default;
+  optional_assign_base(const optional_assign_base&) = default;
+  optional_assign_base(optional_assign_base&&) = default;
+  optional_assign_base& operator=(const optional_assign_base&) = delete;
+  optional_assign_base& operator=(optional_assign_base&&) = default;
+};
+
+template <>
+class optional_assign_base<copy_traits::non_movable> {
+ public:
+  constexpr optional_assign_base() = default;
+  optional_assign_base(const optional_assign_base&) = default;
+  optional_assign_base(optional_assign_base&&) = default;
+  optional_assign_base& operator=(const optional_assign_base&) = delete;
+  optional_assign_base& operator=(optional_assign_base&&) = delete;
+};
+
+template <typename T>
+struct ctor_copy_traits {
+  static constexpr copy_traits traits =
+      std::is_copy_constructible<T>::value
+          ? copy_traits::copyable
+          : std::is_move_constructible<T>::value ? copy_traits::movable
+                                                 : copy_traits::non_movable;
+};
+
+template <typename T>
+struct assign_copy_traits {
+  static constexpr copy_traits traits =
+      absl::is_copy_assignable<T>::value && std::is_copy_constructible<T>::value
+          ? copy_traits::copyable
+          : absl::is_move_assignable<T>::value &&
+                    std::is_move_constructible<T>::value
+                ? copy_traits::movable
+                : copy_traits::non_movable;
+};
+
+// Whether T is constructible or convertible from optional<U>.
+template <typename T, typename U>
+struct is_constructible_convertible_from_optional
+    : std::integral_constant<
+          bool, std::is_constructible<T, optional<U>&>::value ||
+                    std::is_constructible<T, optional<U>&&>::value ||
+                    std::is_constructible<T, const optional<U>&>::value ||
+                    std::is_constructible<T, const optional<U>&&>::value ||
+                    std::is_convertible<optional<U>&, T>::value ||
+                    std::is_convertible<optional<U>&&, T>::value ||
+                    std::is_convertible<const optional<U>&, T>::value ||
+                    std::is_convertible<const optional<U>&&, T>::value> {};
+
+// Whether T is constructible or convertible or assignable from optional<U>.
+template <typename T, typename U>
+struct is_constructible_convertible_assignable_from_optional
+    : std::integral_constant<
+          bool, is_constructible_convertible_from_optional<T, U>::value ||
+                    std::is_assignable<T&, optional<U>&>::value ||
+                    std::is_assignable<T&, optional<U>&&>::value ||
+                    std::is_assignable<T&, const optional<U>&>::value ||
+                    std::is_assignable<T&, const optional<U>&&>::value> {};
+
+// Helper function used by [optional.relops], [optional.comp_with_t],
+// for checking whether an expression is convertible to bool.
+bool convertible_to_bool(bool);
+
+// Base class for std::hash<absl::optional<T>>:
+// If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to
+// compute the hash; Otherwise, it is disabled.
+// Reference N4659 23.14.15 [unord.hash].
+template <typename T, typename = size_t>
+struct optional_hash_base {
+  optional_hash_base() = delete;
+  optional_hash_base(const optional_hash_base&) = delete;
+  optional_hash_base(optional_hash_base&&) = delete;
+  optional_hash_base& operator=(const optional_hash_base&) = delete;
+  optional_hash_base& operator=(optional_hash_base&&) = delete;
+};
+
+template <typename T>
+struct optional_hash_base<T, decltype(std::hash<absl::remove_const_t<T> >()(
+                                 std::declval<absl::remove_const_t<T> >()))> {
+  using argument_type = absl::optional<T>;
+  using result_type = size_t;
+  size_t operator()(const absl::optional<T>& opt) const {
+    absl::type_traits_internal::AssertHashEnabled<absl::remove_const_t<T>>();
+    if (opt) {
+      return std::hash<absl::remove_const_t<T> >()(*opt);
+    } else {
+      return static_cast<size_t>(0x297814aaad196e6dULL);
+    }
+  }
+};
+
+}  // namespace optional_internal
+}  // namespace absl
+
+#endif  // ABSL_TYPES_INTERNAL_OPTIONAL_H_
diff --git a/absl/types/optional.h b/absl/types/optional.h
index 6806160dff7f..17f789847386 100644
--- a/absl/types/optional.h
+++ b/absl/types/optional.h
@@ -35,8 +35,7 @@
 #ifndef ABSL_TYPES_OPTIONAL_H_
 #define ABSL_TYPES_OPTIONAL_H_
 
-#include "absl/base/config.h"
-#include "absl/memory/memory.h"
+#include "absl/base/config.h"   // TODO(calabrese) IWYU removal?
 #include "absl/utility/utility.h"
 
 #ifdef ABSL_HAVE_STD_OPTIONAL
@@ -56,7 +55,6 @@ using std::nullopt;
 #include <cassert>
 #include <functional>
 #include <initializer_list>
-#include <new>
 #include <type_traits>
 #include <utility>
 
@@ -64,6 +62,7 @@ using std::nullopt;
 #include "absl/base/internal/inline_variable.h"
 #include "absl/meta/type_traits.h"
 #include "absl/types/bad_optional_access.h"
+#include "absl/types/internal/optional.h"
 
 // ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
 //
@@ -95,6 +94,22 @@ using std::nullopt;
 
 namespace absl {
 
+// nullopt_t
+//
+// Class type for `absl::nullopt` used to indicate an `absl::optional<T>` type
+// that does not contain a value.
+struct nullopt_t {
+  // It must not be default-constructible to avoid ambiguity for opt = {}.
+  explicit constexpr nullopt_t(optional_internal::init_t) noexcept {}
+};
+
+// nullopt
+//
+// A tag constant of type `absl::nullopt_t` used to indicate an empty
+// `absl::optional` in certain functions, such as construction or assignment.
+ABSL_INTERNAL_INLINE_CONSTEXPR(nullopt_t, nullopt,
+                               nullopt_t(optional_internal::init_t()));
+
 // -----------------------------------------------------------------------------
 // absl::optional
 // -----------------------------------------------------------------------------
@@ -124,361 +139,7 @@ namespace absl {
 //       a) move constructors should only throw due to allocation failure and
 //       b) if T's move constructor allocates, it uses the same allocation
 //          function as the default allocator.
-template <typename T>
-class optional;
-
-namespace optional_internal {
-
-// This tag type is used as a constructor parameter type for `nullopt_t`.
-struct init_t {
-  explicit init_t() = default;
-};
-
-}  // namespace optional_internal
-
-// nullopt_t
-//
-// Class type for `absl::nullopt` used to indicate an `absl::optional<T>` type
-// that does not contain a value.
-struct nullopt_t {
-  // It must not be default-constructible to avoid ambiguity for opt = {}.
-  explicit constexpr nullopt_t(optional_internal::init_t) noexcept {}
-};
-
-// nullopt
 //
-// A tag constant of type `absl::nullopt_t` used to indicate an empty
-// `absl::optional` in certain functions, such as construction or assignment.
-ABSL_INTERNAL_INLINE_CONSTEXPR(nullopt_t, nullopt,
-                               nullopt_t(optional_internal::init_t()));
-
-namespace optional_internal {
-
-struct empty_struct {};
-// This class stores the data in optional<T>.
-// It is specialized based on whether T is trivially destructible.
-// This is the specialization for non trivially destructible type.
-template <typename T, bool unused = std::is_trivially_destructible<T>::value>
-class optional_data_dtor_base {
-  struct dummy_type {
-    static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
-    // Use an array to avoid GCC 6 placement-new warning.
-    empty_struct data[sizeof(T) / sizeof(empty_struct)];
-  };
-
- protected:
-  // Whether there is data or not.
-  bool engaged_;
-  // Data storage
-  union {
-    dummy_type dummy_;
-    T data_;
-  };
-
-  void destruct() noexcept {
-    if (engaged_) {
-      data_.~T();
-      engaged_ = false;
-    }
-  }
-
-  // dummy_ must be initialized for constexpr constructor.
-  constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
-
-  template <typename... Args>
-  constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
-      : engaged_(true), data_(absl::forward<Args>(args)...) {}
-
-  ~optional_data_dtor_base() { destruct(); }
-};
-
-// Specialization for trivially destructible type.
-template <typename T>
-class optional_data_dtor_base<T, true> {
-  struct dummy_type {
-    static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
-    // Use array to avoid GCC 6 placement-new warning.
-    empty_struct data[sizeof(T) / sizeof(empty_struct)];
-  };
-
- protected:
-  // Whether there is data or not.
-  bool engaged_;
-  // Data storage
-  union {
-    dummy_type dummy_;
-    T data_;
-  };
-  void destruct() noexcept { engaged_ = false; }
-
-  // dummy_ must be initialized for constexpr constructor.
-  constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
-
-  template <typename... Args>
-  constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
-      : engaged_(true), data_(absl::forward<Args>(args)...) {}
-};
-
-template <typename T>
-class optional_data_base : public optional_data_dtor_base<T> {
- protected:
-  using base = optional_data_dtor_base<T>;
-#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
-  using base::base;
-#else
-  optional_data_base() = default;
-
-  template <typename... Args>
-  constexpr explicit optional_data_base(in_place_t t, Args&&... args)
-      : base(t, absl::forward<Args>(args)...) {}
-#endif
-
-  template <typename... Args>
-  void construct(Args&&... args) {
-    // Use dummy_'s address to work around casting cv-qualified T* to void*.
-    ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...);
-    this->engaged_ = true;
-  }
-
-  template <typename U>
-  void assign(U&& u) {
-    if (this->engaged_) {
-      this->data_ = std::forward<U>(u);
-    } else {
-      construct(std::forward<U>(u));
-    }
-  }
-};
-
-// TODO(absl-team): Add another class using
-// std::is_trivially_move_constructible trait when available to match
-// http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that
-// have trivial move but nontrivial copy.
-// Also, we should be checking is_trivially_copyable here, which is not
-// supported now, so we use is_trivially_* traits instead.
-template <typename T,
-          bool unused = absl::is_trivially_copy_constructible<T>::value&&
-              absl::is_trivially_copy_assignable<typename std::remove_cv<
-                  T>::type>::value&& std::is_trivially_destructible<T>::value>
-class optional_data;
-
-// Trivially copyable types
-template <typename T>
-class optional_data<T, true> : public optional_data_base<T> {
- protected:
-#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
-  using optional_data_base<T>::optional_data_base;
-#else
-  optional_data() = default;
-
-  template <typename... Args>
-  constexpr explicit optional_data(in_place_t t, Args&&... args)
-      : optional_data_base<T>(t, absl::forward<Args>(args)...) {}
-#endif
-};
-
-template <typename T>
-class optional_data<T, false> : public optional_data_base<T> {
- protected:
-#if ABSL_OPTIONAL_USE_INHERITING_CONSTRUCTORS
-  using optional_data_base<T>::optional_data_base;
-#else
-  template <typename... Args>
-  constexpr explicit optional_data(in_place_t t, Args&&... args)
-      : optional_data_base<T>(t, absl::forward<Args>(args)...) {}
-#endif
-
-  optional_data() = default;
-
-  optional_data(const optional_data& rhs) : optional_data_base<T>() {
-    if (rhs.engaged_) {
-      this->construct(rhs.data_);
-    }
-  }
-
-  optional_data(optional_data&& rhs) noexcept(
-      absl::default_allocator_is_nothrow::value ||
-      std::is_nothrow_move_constructible<T>::value)
-      : optional_data_base<T>() {
-    if (rhs.engaged_) {
-      this->construct(std::move(rhs.data_));
-    }
-  }
-
-  optional_data& operator=(const optional_data& rhs) {
-    if (rhs.engaged_) {
-      this->assign(rhs.data_);
-    } else {
-      this->destruct();
-    }
-    return *this;
-  }
-
-  optional_data& operator=(optional_data&& rhs) noexcept(
-      std::is_nothrow_move_assignable<T>::value&&
-          std::is_nothrow_move_constructible<T>::value) {
-    if (rhs.engaged_) {
-      this->assign(std::move(rhs.data_));
-    } else {
-      this->destruct();
-    }
-    return *this;
-  }
-};
-
-// Ordered by level of restriction, from low to high.
-// Copyable implies movable.
-enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 };
-
-// Base class for enabling/disabling copy/move constructor.
-template <copy_traits>
-class optional_ctor_base;
-
-template <>
-class optional_ctor_base<copy_traits::copyable> {
- public:
-  constexpr optional_ctor_base() = default;
-  optional_ctor_base(const optional_ctor_base&) = default;
-  optional_ctor_base(optional_ctor_base&&) = default;
-  optional_ctor_base& operator=(const optional_ctor_base&) = default;
-  optional_ctor_base& operator=(optional_ctor_base&&) = default;
-};
-
-template <>
-class optional_ctor_base<copy_traits::movable> {
- public:
-  constexpr optional_ctor_base() = default;
-  optional_ctor_base(const optional_ctor_base&) = delete;
-  optional_ctor_base(optional_ctor_base&&) = default;
-  optional_ctor_base& operator=(const optional_ctor_base&) = default;
-  optional_ctor_base& operator=(optional_ctor_base&&) = default;
-};
-
-template <>
-class optional_ctor_base<copy_traits::non_movable> {
- public:
-  constexpr optional_ctor_base() = default;
-  optional_ctor_base(const optional_ctor_base&) = delete;
-  optional_ctor_base(optional_ctor_base&&) = delete;
-  optional_ctor_base& operator=(const optional_ctor_base&) = default;
-  optional_ctor_base& operator=(optional_ctor_base&&) = default;
-};
-
-// Base class for enabling/disabling copy/move assignment.
-template <copy_traits>
-class optional_assign_base;
-
-template <>
-class optional_assign_base<copy_traits::copyable> {
- public:
-  constexpr optional_assign_base() = default;
-  optional_assign_base(const optional_assign_base&) = default;
-  optional_assign_base(optional_assign_base&&) = default;
-  optional_assign_base& operator=(const optional_assign_base&) = default;
-  optional_assign_base& operator=(optional_assign_base&&) = default;
-};
-
-template <>
-class optional_assign_base<copy_traits::movable> {
- public:
-  constexpr optional_assign_base() = default;
-  optional_assign_base(const optional_assign_base&) = default;
-  optional_assign_base(optional_assign_base&&) = default;
-  optional_assign_base& operator=(const optional_assign_base&) = delete;
-  optional_assign_base& operator=(optional_assign_base&&) = default;
-};
-
-template <>
-class optional_assign_base<copy_traits::non_movable> {
- public:
-  constexpr optional_assign_base() = default;
-  optional_assign_base(const optional_assign_base&) = default;
-  optional_assign_base(optional_assign_base&&) = default;
-  optional_assign_base& operator=(const optional_assign_base&) = delete;
-  optional_assign_base& operator=(optional_assign_base&&) = delete;
-};
-
-template <typename T>
-struct ctor_copy_traits {
-  static constexpr copy_traits traits =
-      std::is_copy_constructible<T>::value
-          ? copy_traits::copyable
-          : std::is_move_constructible<T>::value ? copy_traits::movable
-                                                 : copy_traits::non_movable;
-};
-
-template <typename T>
-struct assign_copy_traits {
-  static constexpr copy_traits traits =
-      absl::is_copy_assignable<T>::value && std::is_copy_constructible<T>::value
-          ? copy_traits::copyable
-          : absl::is_move_assignable<T>::value &&
-                    std::is_move_constructible<T>::value
-                ? copy_traits::movable
-                : copy_traits::non_movable;
-};
-
-// Whether T is constructible or convertible from optional<U>.
-template <typename T, typename U>
-struct is_constructible_convertible_from_optional
-    : std::integral_constant<
-          bool, std::is_constructible<T, optional<U>&>::value ||
-                    std::is_constructible<T, optional<U>&&>::value ||
-                    std::is_constructible<T, const optional<U>&>::value ||
-                    std::is_constructible<T, const optional<U>&&>::value ||
-                    std::is_convertible<optional<U>&, T>::value ||
-                    std::is_convertible<optional<U>&&, T>::value ||
-                    std::is_convertible<const optional<U>&, T>::value ||
-                    std::is_convertible<const optional<U>&&, T>::value> {};
-
-// Whether T is constructible or convertible or assignable from optional<U>.
-template <typename T, typename U>
-struct is_constructible_convertible_assignable_from_optional
-    : std::integral_constant<
-          bool, is_constructible_convertible_from_optional<T, U>::value ||
-                    std::is_assignable<T&, optional<U>&>::value ||
-                    std::is_assignable<T&, optional<U>&&>::value ||
-                    std::is_assignable<T&, const optional<U>&>::value ||
-                    std::is_assignable<T&, const optional<U>&&>::value> {};
-
-// Helper function used by [optional.relops], [optional.comp_with_t],
-// for checking whether an expression is convertible to bool.
-bool convertible_to_bool(bool);
-
-// Base class for std::hash<absl::optional<T>>:
-// If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to
-// compute the hash; Otherwise, it is disabled.
-// Reference N4659 23.14.15 [unord.hash].
-template <typename T, typename = size_t>
-struct optional_hash_base {
-  optional_hash_base() = delete;
-  optional_hash_base(const optional_hash_base&) = delete;
-  optional_hash_base(optional_hash_base&&) = delete;
-  optional_hash_base& operator=(const optional_hash_base&) = delete;
-  optional_hash_base& operator=(optional_hash_base&&) = delete;
-};
-
-template <typename T>
-struct optional_hash_base<T, decltype(std::hash<absl::remove_const_t<T> >()(
-                                 std::declval<absl::remove_const_t<T> >()))> {
-  using argument_type = absl::optional<T>;
-  using result_type = size_t;
-  size_t operator()(const absl::optional<T>& opt) const {
-    absl::type_traits_internal::AssertHashEnabled<absl::remove_const_t<T>>();
-    if (opt) {
-      return std::hash<absl::remove_const_t<T> >()(*opt);
-    } else {
-      return static_cast<size_t>(0x297814aaad196e6dULL);
-    }
-  }
-};
-
-}  // namespace optional_internal
-
-// -----------------------------------------------------------------------------
-// absl::optional class definition
-// -----------------------------------------------------------------------------
-
 template <typename T>
 class optional : private optional_internal::optional_data<T>,
                  private optional_internal::optional_ctor_base<
-- 
cgit 1.4.1