// Copyright (C) 2011 - 2012 Andrzej Krzemienski.
//
// Use, modification, and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
// The idea and interface is based on Boost.Optional library
// authored by Fernando Luis Cacciola Carballal
//
// From https://github.com/akrzemi1/Optional
//
// C10
// - Move file to `c10` namespace.
// - Remove macro use in line 478 because the nvcc device compiler cannot handle it
// it.
// - Revise constructor logic so that it is 1) consistent with c++ 17 standard documented
// here in (8): https://en.cppreference.com/w/cpp/utility/optional/optional, and 2)
// able to support initialization of optionals from convertible type U.
// - Remove the constructors for `optional(const T&)` and `optional(T&&)`, as they can be
// handled by the template<U=T> case with the default template argument.
// - Move `constexpr struct in_place_t {} in_place{}` to `c10/util/in_place.h`
// so that it can also be used in `c10/util/variant.h`.
// - Remove special cases for pre-c++14 compilers to make code simpler.

#ifndef C10_UTIL_OPTIONAL_H_
#define C10_UTIL_OPTIONAL_H_

#include <c10/macros/Macros.h>
#include <c10/util/in_place.h>

#include <cassert>
#include <functional>
#include <initializer_list>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>

#include <c10/util/Metaprogramming.h>

#define TR2_OPTIONAL_REQUIRES(...) \
  typename std::enable_if<__VA_ARGS__::value, bool>::type = false

namespace c10 {

// 20.5.4, optional for object types
template <class T>
class optional;

// 20.5.5, optional for lvalue reference types
template <class T>
class optional<T&>;

// workaround: std utility functions aren't constexpr yet
template <class T>
inline constexpr T&& constexpr_forward(
    typename std::remove_reference<T>::type& t) noexcept {
  return static_cast<T&&>(t);
}

template <class T>
inline constexpr T&& constexpr_forward(
    typename std::remove_reference<T>::type&& t) noexcept {
  static_assert(!std::is_lvalue_reference<T>::value, "!!");
  return static_cast<T&&>(t);
}

template <class T>
inline constexpr typename std::remove_reference<T>::type&& constexpr_move(
    T&& t) noexcept {
  return static_cast<typename std::remove_reference<T>::type&&>(t);
}

#if defined NDEBUG
#define TR2_OPTIONAL_ASSERTED_EXPRESSION(CHECK, EXPR) (EXPR)
#else
#define TR2_OPTIONAL_ASSERTED_EXPRESSION(CHECK, EXPR) \
  ((CHECK) ? (EXPR) : ([] { assert(!#CHECK); }(), (EXPR)))
#endif

#if defined(__CUDA_ARCH__)
#define TR2_OPTIONAL_HOST_CONSTEXPR
#else
#define TR2_OPTIONAL_HOST_CONSTEXPR constexpr
#endif

// Sphinx chokes on static_addressof, so exclude it from Doxygen
// generation.  See https://github.com/sphinx-doc/sphinx/issues/7944
// \cond

namespace detail_ {

// VS doesn't handle constexpr well, so we need to skip these stuff.
#if (defined _MSC_VER)
template <typename T>
T* static_addressof(T& ref) {
  return std::addressof(ref);
}
#else
// static_addressof: a constexpr version of addressof
template <typename T>
struct has_overloaded_addressof {
  template <class X>
  constexpr static bool has_overload(...) {
    return false;
  }

  template <class X, size_t S = sizeof(std::declval<X&>().operator&())>
  constexpr static bool has_overload(bool) {
    return true;
  }

  constexpr static bool value = has_overload<T>(true);
};

template <typename T, TR2_OPTIONAL_REQUIRES(!has_overloaded_addressof<T>)>
constexpr T* static_addressof(T& ref) {
  return &ref;
}

template <typename T, TR2_OPTIONAL_REQUIRES(has_overloaded_addressof<T>)>
T* static_addressof(T& ref) {
  return std::addressof(ref);
}
#endif

// the call to convert<A>(b) has return type A and converts b to type A iff b
// decltype(b) is implicitly convertible to A
template <class U>
constexpr U convert(U v) {
  return v;
}

} // namespace detail_

// \endcond

constexpr struct trivial_init_t {
} trivial_init{};

// 20.5.7, Disengaged state indicator
struct nullopt_t {
  constexpr explicit nullopt_t(int) {}
};
constexpr nullopt_t nullopt {0};

// 20.5.8, class bad_optional_access
class bad_optional_access : public std::logic_error {
 public:
  explicit bad_optional_access(const std::string& what_arg)
      : logic_error{what_arg} {}
  explicit bad_optional_access(const char* what_arg) : logic_error{what_arg} {}
};

template <class T>
union storage_t {
  unsigned char dummy_;
  T value_;

  constexpr storage_t(trivial_init_t) noexcept : dummy_(){};

  template <class... Args>
  constexpr storage_t(Args&&... args)
      : value_(constexpr_forward<Args>(args)...) {}

  ~storage_t() {}
};

template <class T>
union constexpr_storage_t {
  unsigned char dummy_;
  T value_;

  constexpr constexpr_storage_t(trivial_init_t) noexcept : dummy_(){};

  template <class... Args>
  constexpr constexpr_storage_t(Args&&... args)
      : value_(constexpr_forward<Args>(args)...) {}

  ~constexpr_storage_t() = default;
};

template <class T>
struct optional_base {
  bool init_;
  storage_t<T> storage_;

  constexpr optional_base() noexcept : init_(false), storage_(trivial_init){};

  explicit constexpr optional_base(const optional_base<T>& v) : init_(v.init_), storage_(trivial_init) {
    if (init_) {
      ::new (dataptr()) T(v.storage_.value_);
    }
  }

  explicit constexpr optional_base(const T& v) : init_(true), storage_(v) {}

  explicit constexpr optional_base(optional_base<T>&& v) noexcept(
      std::is_nothrow_move_constructible<T>::value)
      : init_(v.init_), storage_(trivial_init) {
    if (init_) {
      ::new (dataptr()) T(std::move(v.storage_.value_));
    }
  }

  explicit constexpr optional_base(T&& v)
      : init_(true), storage_(constexpr_move(v)) {}

  template <class... Args>
  explicit optional_base(in_place_t, Args&&... args)
      : init_(true), storage_(constexpr_forward<Args>(args)...) {}

  template <
      class U,
      class... Args,
      TR2_OPTIONAL_REQUIRES(std::is_constructible<T, std::initializer_list<U>>)>
  explicit optional_base(
      in_place_t,
      std::initializer_list<U> il,
      Args&&... args)
      : init_(true), storage_(il, std::forward<Args>(args)...) {}

  optional_base& operator=(const optional_base& rhs) {
    if (init_ && !rhs.init_) {
      clear();
    } else if (!init_ && rhs.init_) {
      init_ = true;
      ::new (dataptr()) T(rhs.storage_.value_);
    } else if (init_ && rhs.init_) {
      storage_.value_ = rhs.storage_.value_;
    }
    return *this;
  }

  optional_base& operator=(optional_base&& rhs) noexcept(
      std::is_nothrow_move_assignable<T>::value &&
          std::is_nothrow_move_constructible<T>::value) {
    if (init_ && !rhs.init_) {
      clear();
    } else if (!init_ && rhs.init_) {
      init_ = true;
      ::new (dataptr()) T(std::move(rhs.storage_.value_));
    } else if (init_ && rhs.init_) {
      storage_.value_ = std::move(rhs.storage_.value_);
    }
    return *this;
  }

  ~optional_base() {
    if (init_)
      storage_.value_.T::~T();
  }

 private:
  typename std::remove_const<T>::type* dataptr() {
    return std::addressof(storage_.value_);
  }

  constexpr const T* dataptr() const {
    return detail_::static_addressof(storage_.value_);
  }

  void clear() noexcept {
    if (init_) {
      dataptr()->~T();
    }
    init_ = false;
  }
};

template <class T>
struct constexpr_optional_base {
  bool init_;
  constexpr_storage_t<T> storage_;

  constexpr constexpr_optional_base() noexcept
      : init_(false), storage_(trivial_init){};

  explicit constexpr constexpr_optional_base(const constexpr_optional_base<T>& v) : init_(v.init_), storage_(trivial_init) {
    if (init_) {
      ::new (dataptr()) T(v.storage_.value_);
    }
  }

  explicit constexpr constexpr_optional_base(constexpr_optional_base<T>&& v) noexcept(
      std::is_nothrow_move_constructible<T>::value)
      : init_(v.init_), storage_(trivial_init) {
    if (init_) {
      ::new (dataptr()) T(std::move(v.storage_.value_));
    }
  }

  explicit constexpr constexpr_optional_base(const T& v)
      : init_(true), storage_(v) {}

  explicit constexpr constexpr_optional_base(T&& v)
      : init_(true), storage_(constexpr_move(v)) {}

  template <class... Args>
  explicit constexpr constexpr_optional_base(in_place_t, Args&&... args)
      : init_(true), storage_(constexpr_forward<Args>(args)...) {}

  template <
      class U,
      class... Args,
      TR2_OPTIONAL_REQUIRES(std::is_constructible<T, std::initializer_list<U>>)>
  constexpr explicit constexpr_optional_base(
      in_place_t,
      std::initializer_list<U> il,
      Args&&... args)
      : init_(true), storage_(il, std::forward<Args>(args)...) {}

  ~constexpr_optional_base() = default;

  constexpr_optional_base& operator=(const constexpr_optional_base& rhs) {
    if (init_ && !rhs.init_) {
      clear();
    } else if (!init_ && rhs.init_) {
      init_ = true;
      ::new (dataptr()) T(rhs.storage_.value_);
    } else if (init_ && rhs.init_) {
      storage_.value_ = rhs.storage_.value_;
    }
    return *this;
  }

  constexpr_optional_base& operator=(constexpr_optional_base&& rhs) noexcept(
      std::is_nothrow_move_assignable<T>::value &&
          std::is_nothrow_move_constructible<T>::value) {
    if (init_ && !rhs.init_) {
      clear();
    } else if (!init_ && rhs.init_) {
      init_ = true;
      ::new (dataptr()) T(std::move(rhs.storage_.value_));
    } else if (init_ && rhs.init_) {
      storage_.value_ = std::move(rhs.storage_.value_);
    }
    return *this;
  }

 private:
  typename std::remove_const<T>::type* dataptr() {
    return std::addressof(storage_.value_);
  }