chromium/third_party/abseil-cpp/absl/types/internal/variant.h

// Copyright 2018 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.
//
// Implementation details of absl/types/variant.h, pulled into a
// separate file to avoid cluttering the top of the API header with
// implementation details.

#ifndef ABSL_TYPES_INTERNAL_VARIANT_H_
#define ABSL_TYPES_INTERNAL_VARIANT_H_

#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <memory>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <utility>

#include "absl/base/config.h"
#include "absl/base/internal/identity.h"
#include "absl/base/internal/inline_variable.h"
#include "absl/base/internal/invoke.h"
#include "absl/base/macros.h"
#include "absl/base/optimization.h"
#include "absl/meta/type_traits.h"
#include "absl/types/bad_variant_access.h"
#include "absl/utility/utility.h"

#if !defined(ABSL_USES_STD_VARIANT)

namespace absl {
ABSL_NAMESPACE_BEGIN

template <class... Types>
class variant;

ABSL_INTERNAL_INLINE_CONSTEXPR(size_t, variant_npos, static_cast<size_t>(-1));

template <class T>
struct variant_size;

template <std::size_t I, class T>
struct variant_alternative;

namespace variant_internal {

// NOTE: See specializations below for details.
template <std::size_t I, class T>
struct VariantAlternativeSfinae { … };

// Requires: I < variant_size_v<T>.
//
// Value: The Ith type of Types...
VariantAlternativeSfinae<I, variant<T0, Tn...>>;

// Value: T0
VariantAlternativeSfinae<0, variant<T0, Ts...>>;

VariantAlternativeSfinaeT;

// NOTE: Requires T to be a reference type.
template <class T, class U>
struct GiveQualsTo;

GiveQualsTo<T &, U>;

GiveQualsTo<T &&, U>;

GiveQualsTo<const T &, U>;

GiveQualsTo<const T &&, U>;

GiveQualsTo<volatile T &, U>;

GiveQualsTo<volatile T &&, U>;

GiveQualsTo<const volatile T &, U>;

GiveQualsTo<const volatile T &&, U>;

GiveQualsToT;

// Convenience alias, since size_t integral_constant is used a lot in this file.
SizeT;

NPos;

template <class Variant, class T, class = void>
struct IndexOfConstructedType { … };

template <std::size_t I, class Variant>
struct VariantAccessResultImpl;

VariantAccessResultImpl<I, Variantemplate<T...> &>;

VariantAccessResultImpl<I, const Variantemplate<T...> &>;

VariantAccessResultImpl<I, Variantemplate<T...> &&>;

VariantAccessResultImpl<I, const Variantemplate<T...> &&>;

VariantAccessResult;

// NOTE: This is used instead of std::array to reduce instantiation overhead.
template <class T, std::size_t Size>
struct SimpleArray { … };

template <class T>
struct AccessedType { … };

AccessedTypeT;

AccessedType<SimpleArray<T, Size>>;

template <class T>
constexpr T AccessSimpleArray(const T& value) { … }

template <class T, std::size_t Size, class... SizeT>
constexpr AccessedTypeT<T> AccessSimpleArray(const SimpleArray<T, Size>& table,
                                             std::size_t head_index,
                                             SizeT... tail_indices) { … }

// Note: Intentionally is an alias.
AlwaysZero;

template <class Op, class... Vs>
struct VisitIndicesResultImpl { … };

VisitIndicesResultT;

template <class ReturnType, class FunctionObject, class EndIndices,
          class BoundIndices>
struct MakeVisitationMatrix;

template <class ReturnType, class FunctionObject, std::size_t... Indices>
constexpr ReturnType call_with_indices(FunctionObject&& function) { … }

MakeVisitationMatrix<ReturnType, FunctionObject, index_sequence<>, index_sequence<BoundIndices...>>;

template <typename Is, std::size_t J>
struct AppendToIndexSequence;

AppendToIndexSequenceT;

AppendToIndexSequence<index_sequence<Is...>, J>;

template <class ReturnType, class FunctionObject, class EndIndices,
          class CurrIndices, class BoundIndices>
struct MakeVisitationMatrixImpl;

MakeVisitationMatrixImpl<ReturnType, FunctionObject, EndIndices, index_sequence<CurrIndices...>, BoundIndices>;

MakeVisitationMatrix<ReturnType, FunctionObject, index_sequence<HeadEndIndex, TailEndIndices...>, index_sequence<BoundIndices...>>;

struct UnreachableSwitchCase { … };

template <class Op, std::size_t I>
struct ReachableSwitchCase { … };

// The number 33 is just a guess at a reasonable maximum to our switch. It is
// not based on any analysis. The reason it is a power of 2 plus 1 instead of a
// power of 2 is because the number was picked to correspond to a power of 2
// amount of "normal" alternatives, plus one for the possibility of the user
// providing "monostate" in addition to the more natural alternatives.
ABSL_INTERNAL_INLINE_CONSTEXPR(std::size_t, MaxUnrolledVisitCases, 33);

// Note: The default-definition is for unreachable cases.
template <bool IsReachable>
struct PickCaseImpl { … };

template <>
struct PickCaseImpl</*IsReachable =*/true> { … };

// Note: This form of dance with template aliases is to make sure that we
//       instantiate a number of templates proportional to the number of variant
//       alternatives rather than a number of templates proportional to our
//       maximum unrolled amount of visitation cases (aliases are effectively
//       "free" whereas other template instantiations are costly).
PickCase;

template <class ReturnType>
[[noreturn]] ReturnType TypedThrowBadVariantAccess() { … }

// Given N variant sizes, determine the number of cases there would need to be
// in a single switch-statement that would cover every possibility in the
// corresponding N-ary visit operation.
template <std::size_t... NumAlternatives>
struct NumCasesOfSwitch;

NumCasesOfSwitch<HeadNumAlternatives, TailNumAlternatives...>;

template <>
struct NumCasesOfSwitch<> { … };

// A switch statement optimizes better than the table of function pointers.
template <std::size_t EndIndex>
struct VisitIndicesSwitch { … };

template <std::size_t... EndIndices>
struct VisitIndicesFallback { … };

// Take an N-dimensional series of indices and convert them into a single index
// without loss of information. The purpose of this is to be able to convert an
// N-ary visit operation into a single switch statement.
template <std::size_t...>
struct FlattenIndices;

FlattenIndices<HeadSize, TailSize...>;

template <>
struct FlattenIndices<> { … };

// Take a single "flattened" index (flattened by FlattenIndices) and determine
// the value of the index of one of the logically represented dimensions.
template <std::size_t I, std::size_t IndexToGet, std::size_t HeadSize,
          std::size_t... TailSize>
struct UnflattenIndex { … };

UnflattenIndex<I, 0, HeadSize, TailSize...>;

// The backend for converting an N-ary visit operation into a unary visit.
template <class IndexSequence, std::size_t... EndIndices>
struct VisitIndicesVariadicImpl;

VisitIndicesVariadicImpl<absl::index_sequence<N...>, EndIndices...>;

template <std::size_t... EndIndices>
struct VisitIndicesVariadic
    : VisitIndicesVariadicImpl<absl::make_index_sequence<sizeof...(EndIndices)>,
                               EndIndices...> { … };

// This implementation will flatten N-ary visit operations into a single switch
// statement when the number of cases would be less than our maximum specified
// switch-statement size.
// TODO(calabrese)
//   Based on benchmarks, determine whether the function table approach actually
//   does optimize better than a chain of switch statements and possibly update
//   the implementation accordingly. Also consider increasing the maximum switch
//   size.
template <std::size_t... EndIndices>
struct VisitIndices
    : absl::conditional_t<(NumCasesOfSwitch<EndIndices...>::value <=
                           MaxUnrolledVisitCases),
                          VisitIndicesVariadic<EndIndices...>,
                          VisitIndicesFallback<EndIndices...>> { … };

VisitIndices<EndIndex>;

// Suppress bogus warning on MSVC: MSVC complains that the `reinterpret_cast`
// below is returning the address of a temporary or local object.
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4172)
#endif  // _MSC_VER

// TODO(calabrese) std::launder
// TODO(calabrese) constexpr
// NOTE: DO NOT REMOVE the `inline` keyword as it is necessary to work around a
// MSVC bug. See https://github.com/abseil/abseil-cpp/issues/129 for details.
template <class Self, std::size_t I>
inline VariantAccessResult<I, Self> AccessUnion(Self&& self, SizeT<I> /*i*/) { … }

#ifdef _MSC_VER
#pragma warning(pop)
#endif  // _MSC_VER

template <class T>
void DeducedDestroy(T& self) { … }

// NOTE: This type exists as a single entity for variant and its bases to
// befriend. It contains helper functionality that manipulates the state of the
// variant, such as the implementation of things like assignment and emplace
// operations.
struct VariantCoreAccess { … };

template <class Expected, class... T>
struct IndexOfImpl;

IndexOfImpl<Expected>;

IndexOfImpl<Expected, Head, Tail...>;

IndexOfImpl<Expected, Expected, Tail...>;

template <class Expected, class... Types>
struct IndexOfMeta { … };

IndexOf;

template <class Variant, class T, std::size_t CurrIndex>
struct UnambiguousIndexOfImpl;

// Terminating case encountered once we've checked all of the alternatives
UnambiguousIndexOfImpl<variant<>, T, CurrIndex>;

// Case where T is not Head
UnambiguousIndexOfImpl<variant<Head, Tail...>, T, CurrIndex>;

// Case where T is Head
UnambiguousIndexOfImpl<variant<Head, Tail...>, Head, CurrIndex>;

template <class Variant, class T>
struct UnambiguousIndexOf;

struct NoMatch { … };

UnambiguousIndexOf<variant<Alts...>, T>;

UnambiguousTypeOfImpl;

UnambiguousTypeOfT;

template <class H, class... T>
class VariantStateBase;

// This is an implementation of the "imaginary function" that is described in
// [variant.ctor]
// It is used in order to determine which alternative to construct during
// initialization from some type T.
template <class Variant, std::size_t I = 0>
struct ImaginaryFun;

ImaginaryFun<variant<>, I>;

ImaginaryFun<variant<H, T...>, I>;

// The following metafunctions are used in constructor and assignment
// constraints.
template <class Self, class T>
struct IsNeitherSelfNorInPlace : std::true_type { … };

IsNeitherSelfNorInPlace<Self, Self>;

IsNeitherSelfNorInPlace<Self, in_place_type_t<T>>;

IsNeitherSelfNorInPlace<Self, in_place_index_t<I>>;

IndexOfConstructedType<Variant, T, void_t<decltype(ImaginaryFun<Variant>::Run(std::declval<T>(), {}))>>;

template <std::size_t... Is>
struct ContainsVariantNPos
    : absl::negation<std::is_same<  // NOLINT
          std::integer_sequence<bool, 0 <= Is...>,
          std::integer_sequence<bool, Is != absl::variant_npos...>>> { … };

RawVisitResult;

// NOTE: The spec requires that all return-paths yield the same type and is not
// SFINAE-friendly, so we can deduce the return type by examining the first
// result. If it's not callable, then we get an error, but are compliant and
// fast to compile.
// TODO(calabrese) Possibly rewrite in a way that yields better compile errors
// at the cost of longer compile-times.
template <class Op, class... QualifiedVariants>
struct VisitResultImpl { … };

// Done in two steps intentionally so that we don't cause substitution to fail.
VisitResult;

template <class Op, class... QualifiedVariants>
struct PerformVisitation { … };

template <class... T>
union Union;

// We want to allow for variant<> to be trivial. For that, we need the default
// constructor to be trivial, which means we can't define it ourselves.
// Instead, we use a non-default constructor that takes NoopConstructorTag
// that doesn't affect the triviality of the types.
struct NoopConstructorTag { … };

template <std::size_t I>
struct EmplaceTag { … };

Union<>;

// Suppress bogus warning on MSVC: MSVC complains that Union<T...> has a defined
// deleted destructor from the `std::is_destructible` check below.
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4624)
#endif  // _MSC_VER

Union<Head, Tail...>;

#ifdef _MSC_VER
#pragma warning(pop)
#endif  // _MSC_VER

// TODO(calabrese) Just contain a Union in this union (certain configs fail).
template <class... T>
union DestructibleUnionImpl;

DestructibleUnionImpl<>;

DestructibleUnionImpl<Head, Tail...>;

// This union type is destructible even if one or more T are not trivially
// destructible. In the case that all T are trivially destructible, then so is
// this resultant type.
DestructibleUnion;

// Deepest base, containing the actual union and the discriminator
template <class H, class... T>
class VariantStateBase { … };

type_identity;

// OverloadSet::Overload() is a unary function which is overloaded to
// take any of the element types of the variant, by reference-to-const.
// The return type of the overload on T is type_identity<T>, so that you
// can statically determine which overload was called.
//
// Overload() is not defined, so it can only be called in unevaluated
// contexts.
template <typename... Ts>
struct OverloadSet;

OverloadSet<T, Ts...>;

template <>
struct OverloadSet<> { … };

LessThanResult;

GreaterThanResult;

LessThanOrEqualResult;

GreaterThanOrEqualResult;

EqualResult;

NotEqualResult;

is_detected_convertible;

RequireAllHaveEqualT;

RequireAllHaveNotEqualT;

RequireAllHaveLessThanT;

RequireAllHaveLessThanOrEqualT;

RequireAllHaveGreaterThanOrEqualT;

RequireAllHaveGreaterThanT;

// Helper template containing implementations details of variant that can't go
// in the private section. For convenience, this takes the variant type as a
// single template parameter.
template <typename T>
struct VariantHelper;

VariantHelper<variant<Ts...>>;

// A type with nontrivial copy ctor and trivial move ctor.
struct TrivialMoveOnly { … };

// Trait class to detect whether a type is trivially move constructible.
// A union's defaulted copy/move constructor is deleted if any variant member's
// copy/move constructor is nontrivial.
template <typename T>
struct IsTriviallyMoveConstructible
    : std::is_move_constructible<Union<T, TrivialMoveOnly>> { … };

// To guarantee triviality of all special-member functions that can be trivial,
// we use a chain of conditional bases for each one.
// The order of inheritance of bases from child to base are logically:
//
// variant
// VariantCopyAssignBase
// VariantMoveAssignBase
// VariantCopyBase
// VariantMoveBase
// VariantStateBaseDestructor
// VariantStateBase
//
// Note that there is a separate branch at each base that is dependent on
// whether or not that corresponding special-member-function can be trivial in
// the resultant variant type.

template <class... T>
class VariantStateBaseDestructorNontrivial;

template <class... T>
class VariantMoveBaseNontrivial;

template <class... T>
class VariantCopyBaseNontrivial;

template <class... T>
class VariantMoveAssignBaseNontrivial;

template <class... T>
class VariantCopyAssignBaseNontrivial;

// Base that is dependent on whether or not the destructor can be trivial.
VariantStateBaseDestructor;

// Base that is dependent on whether or not the move-constructor can be
// implicitly generated by the compiler (trivial or deleted).
// Previously we were using `std::is_move_constructible<Union<T...>>` to check
// whether all Ts have trivial move constructor, but it ran into a GCC bug:
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84866
// So we have to use a different approach (i.e. `HasTrivialMoveConstructor`) to
// work around the bug.
VariantMoveBase;

// Base that is dependent on whether or not the copy-constructor can be trivial.
VariantCopyBase;

// Base that is dependent on whether or not the move-assign can be trivial.
VariantMoveAssignBase;

// Base that is dependent on whether or not the copy-assign can be trivial.
VariantCopyAssignBase;

VariantBase;

template <class... T>
class VariantStateBaseDestructorNontrivial : protected VariantStateBase<T...> { … };

template <class... T>
class VariantMoveBaseNontrivial : protected VariantStateBaseDestructor<T...> { … };

template <class... T>
class VariantCopyBaseNontrivial : protected VariantMoveBase<T...> { … };

template <class... T>
class VariantMoveAssignBaseNontrivial : protected VariantCopyBase<T...> { … };

template <class... T>
class VariantCopyAssignBaseNontrivial : protected VariantMoveAssignBase<T...> { … };

////////////////////////////////////////
// Visitors for Comparison Operations //
////////////////////////////////////////

template <class... Types>
struct EqualsOp { … };

template <class... Types>
struct NotEqualsOp { … };

template <class... Types>
struct LessThanOp { … };

template <class... Types>
struct GreaterThanOp { … };

template <class... Types>
struct LessThanOrEqualsOp { … };

template <class... Types>
struct GreaterThanOrEqualsOp { … };

// Precondition: v.index() == w.index();
template <class... Types>
struct SwapSameIndex { … };

// TODO(calabrese) do this from a different namespace for proper adl usage
template <class... Types>
struct Swap { … };

template <typename Variant, typename = void, typename... Ts>
struct VariantHashBase { … };

struct VariantHashVisitor { … };

VariantHashBase<Variant, absl::enable_if_t<absl::conjunction<type_traits_internal::IsHashable<Ts>...>::value>, Ts...>;

}  // namespace variant_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // !defined(ABSL_USES_STD_VARIANT)
#endif  // ABSL_TYPES_INTERNAL_VARIANT_H_