#ifndef BOOST_OPENMETHOD_REGISTRY_HPP
#define BOOST_OPENMETHOD_REGISTRY_HPP

#include <boost/openmethod/detail/static_list.hpp>

#include <boost/config.hpp>
#include <boost/mp11/algorithm.hpp>
#include <boost/mp11/bind.hpp>
#include <boost/mp11/utility.hpp>
#include <boost/preprocessor/cat.hpp>

#include <stdlib.h>
#include <vector>
#include <cstdint>
#include <string_view>
#include <tuple>

#ifdef _MSC_VER
#pragma warning(push)
// 4702: unreachable code. 4251: registry_state<R>::st (dll-exported) has type
// registry_state_type<R>, which intentionally has no dll-interface; benign for
// a static member, which is not part of object layout.
#pragma warning(disable : 4702 4251)
#endif

namespace boost::openmethod {

// -----------------------------------------------------------------------------
// word

namespace detail {

union word {
    word() {
    } // undefined
    word(void (*pf)()) : pf(pf) {
    }
    word(word* pw) : pw(pw) {
    }
    word(std::size_t i) : i(i) {
    }

    void (*pf)();
    std::size_t i;
    word* pw;
};

} // namespace detail

// -----------------------------------------------------------------------------
// public aliases

//! Alias to v-table pointer type.
//!
//! `vptr_type` is an alias to the type of a v-table pointer.
using vptr_type = const detail::word*;

//! Type used to identify a class.
//!
//! `type_id` is the return type of the @ref static_type and @ref dynamic_type
//! functions. It can be used as an actual data pointer (e.g. to a
//! `std::type_info` object), or as an opaque integer type.
using type_id = const void*;

// -----------------------------------------------------------------------------
// virtual types and traits

//! Decorator for virtual parameters.
//!
//! `virtual_` marks a formal parameter of a method as virtual. It is a @em
//! decorator, not an actual type that can be instantiated (it does not have a
//! definition). It is removed from the method's signature.
//!
//! @note `virtual_` can be used @em only in method declarations, @em not in
//! overriders. A parameter in overriders is implicitly virtual if it is in
//! the same position as a virtual parameter in the method's declaration.
//!
//! @par Requirements
//!
//! - @ref virtual_traits must be specialized for `T`.
//!
//! @tparam T A class.
//!
//! @see [Virtual Pointer Alternatives](xref:ROOT:virtual_ptr_alt.adoc)
template<typename T>
struct virtual_;

template<typename T, class Registry>
struct virtual_traits;

// =============================================================================
// Error handling

//! Base class for all OpenMethod errors.
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct openmethod_error {};

//! One Definition Rule violation.
//!
//! This error is raised if the definition of @ref default_registry is
//! inconsistent across translation units, due to misuse of
//! @ref BOOST_OPENMETHOD_ENABLE_RUNTIME_CHECKS.
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct odr_violation : openmethod_error {
    //! Write a description of the error to a stream.
    //! @tparam Registry The registry containing this policy.
    //! @param stream The stream to write to.
    template<class Registry, class Stream>
    auto write(Stream& stream) const {
        stream << "conflicting definitions of ";
        Registry::rtti::type_name(
            Registry::rtti::template static_type<Registry>(), stream);
    }
};

namespace detail {

template<class Registry>
struct BOOST_SYMBOL_VISIBLE odr_check {
    static std::size_t count;
    template<class R>
    static std::size_t inc;

    odr_check() {
        [[maybe_unused]] auto _ = &inc<typename Registry::registry_type>;
    }
};

template<class Registry>
std::size_t odr_check<Registry>::count;

template<class Registry>
template<class R>
std::size_t odr_check<Registry>::inc = count++;

} // namespace detail

//! Registry not initialized
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct not_initialized : openmethod_error {
    //! Write a short description to an output stream
    //! @param os The output stream
    //! @tparam Registry The registry
    //! @tparam Stream A @ref LightweightOutputStream
    template<class Registry, class Stream>
    auto write(Stream& os) const {
        os << "not initialized";
    }
};

//! Missing class.
//!
//! A class used as a virtual parameter in a method, an overrider or a method
//! call was not registered.
//!
//! @par Examples
//!
//! @note The error goes to the registry's
//! @ref boost::openmethod::policies::error_handler policy, which writes the
//! description shown in the comments; the program is then terminated. A
//! handler may throw instead, to keep the program running.
//!
//! Missing registration of a class used as a virtual parameter in a method:
//!
//! include:errors_missing_class_method.cpp#classes;init
//!
//! Missing registration of a class used as a virtual parameter in an overrider:
//!
//! include:errors_missing_class_overrider.cpp#classes;init
//!
//! Missing registration of a class used as a virtual parameter in a call:
//!
//! include:errors_missing_class_call.cpp#classes;use
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct missing_class : openmethod_error {
    //! The type_id of the unknown class.
    type_id type;

    //! Write a short description to an output stream
    //! @param os The output stream
    //! @tparam Registry The registry
    //! @tparam Stream A @ref LightweightOutputStream
    template<class Registry, class Stream>
    auto write(Stream& os) const;
};

//! Missing base.
//!
//! A class used in an overrider virtual parameter was not registered as a
//! derived class of the class in the same position in the method's virtual
//! parameter list.
//!
//! @par Example
//!
//! @note The error goes to the registry's
//! @ref boost::openmethod::policies::error_handler policy, which writes the
//! description shown in the comments; the program is then terminated. A
//! handler may throw instead, to keep the program running.
//!
//! In the following code, OpenMethod cannot infer that `Dog` is derived from
//! `Animal`, because they are not registered in a same call to @ref
//! BOOST_OPENMETHOD_CLASSES.
//!
//! include:errors_missing_base.cpp#classes;init
//!
//! Fix:
//!
//! include:errors_missing_class_call.cpp#fix
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct missing_base : openmethod_error {
    //! The type_id of the base class.
    type_id base;
    //! The type_id of the derived class.
    type_id derived;

    //! Write a short description to an output stream
    //! @param os The output stream
    //! @tparam Registry The registry
    //! @tparam Stream A @ref LightweightOutputStream
    template<class Registry, class Stream>
    auto write(Stream& os) const;
};

//! No valid overrider
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct bad_call : openmethod_error {
    //! The type_id of method that was called
    type_id method;
    //! The number of @em virtual arguments in the call
    std::size_t arity;
    //! The maximum size of `types`
    static constexpr std::size_t max_types = 16;
    //! The type_ids of the arguments.
    type_id types[max_types];
};

//! No overrider for virtual tuple
//!
//! The data members are documented on @ref bad_call.
//!
//! @see @ref bad_call
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct no_overrider : bad_call {
    //! Write a short description to an output stream
    //! @param os The output stream
    //! @tparam Registry The registry
    //! @tparam Stream A @ref LightweightOutputStream
    template<class Registry, class Stream>
    auto write(Stream& os) const {
        os << "not implemented";
    }
};

//! Ambiguous call
//!
//! The data members are documented on @ref bad_call.
//!
//! @see @ref bad_call
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct ambiguous_call : bad_call {
    //! Write a short description to an output stream
    //! @param os The output stream
    //! @tparam Registry The registry
    //! @tparam Stream A @ref LightweightOutputStream
    template<class Registry, class Stream>
    auto write(Stream& os) const {
        os << "ambiguous";
    }
};

//! Static and dynamic type mismatch in "final" construct
//!
//! If runtime checks are enabled, the "final" construct checks that the static
//! and dynamic types of the object, as reported by the `rtti` policy,  are the
//! same. If they are not, and if the registry contains an @ref error_handler
//! policy, its @ref error function is called with a `final_error` object, then
//! the program is terminated with
//! @ref abort.
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct final_error : openmethod_error {
    type_id static_type, dynamic_type;

    //! Write a short description to an output stream
    //! @param os The output stream
    //! @tparam Registry The registry
    //! @tparam Stream A @ref LightweightOutputStream
    template<class Registry, class Stream>
    auto write(Stream& os) const;
};

namespace detail {

// =============================================================================
// generic registrars

// -----------------------------------------------------------------------------
// class info

struct class_info : static_list<class_info>::static_link {
    type_id type;
    vptr_type* static_vptr;
    type_id *first_base, *last_base;
    bool is_abstract{false};

    auto vptr() const -> const vptr_type& {
        return *static_vptr;
    }

    auto type_id_begin() const {
        return &type;
    }

    auto type_id_end() const {
        return &type + 1;
    }
};

struct deferred_class_info : class_info {
    virtual void resolve_type_ids() = 0;
};

// -----------
// method info

struct overrider_info;

struct method_info : static_list<method_info>::static_link {
    type_id* vp_begin;
    type_id* vp_end;
    static_list<overrider_info> overriders;
    void (*not_implemented)();
    void (*ambiguous)();
    type_id method_type_id;
    type_id return_type_id;
    std::size_t* slots_strides_ptr;

    auto arity() const {
        return std::distance(vp_begin, vp_end);
    }
};

struct deferred_method_info : method_info {
    virtual void resolve_type_ids() = 0;
};

struct overrider_info : static_list<overrider_info>::static_link {
    ~overrider_info() {
        method->overriders.remove(*this);
    }

    method_info* method; // for the destructor, to remove definition
    type_id return_type; // for N2216 disambiguation
    type_id type;        // of the function, for trace
    void (**next)();
    type_id *vp_begin, *vp_end;
    void (*pf)();
    // Set by BOOST_OPENMETHOD_INLINE_OVERRIDE (see the Inline template
    // parameter of override_impl/override_aux and class inline_override in
    // core.hpp). Only an overrider defined `inline` can legally have an
    // identical definition appear in more than one translation unit/module
    // (ODR requires it for a non-template, non-inline function to be defined
    // exactly once in the program), so augment_methods()'s cross-module
    // dedup only ever merges two overrider_info entries when both have
    // inline_ == true.
    bool inline_ = false;
};

struct deferred_overrider_info : overrider_info {
    virtual void resolve_type_ids() = 0;
};

} // namespace detail

// =============================================================================
// initialize options

#ifdef __MRDOCS__

namespace detail {
struct unspecified {};
} // namespace detail

//! Blueprint for a lightweight output stream (exposition only).
//!
//! Classes used as output streams in policies must provide the operations
//! described on this page, either as members or as free functions.
struct LightweightOutputStream {
    //! Writes a null-terminated string to the stream.
    LightweightOutputStream& operator<<(const char* str);

    //! Writes a string view to the stream.
    LightweightOutputStream& operator<<(const std::string_view& view);

    //! Writes a pointer value to the stream.
    LightweightOutputStream& operator<<(const void* value);

    //! Writes a size_t value to the stream.
    LightweightOutputStream& operator<<(std::size_t value);
};

#endif

// -----------------------------------------------------------------------------
// n2216

//! N2216 ambiguity resolution.
//!
//! If `n2216` is present in @ref initialize\'s `Options`, additional steps are
//! taken to select a single overrider in presence of ambiguous overriders sets,
//! according to the rules defined in the N2216 paper. If the normal resolution
//! procedure fails to select a single overrider, the following steps are
//! applied, in order:
//!
//! - If the return types of the remaining overriders are all polymorphic and
//!   covariant, and one of the return types is more specialized thjat all the
//!   others, use it.
//!
//! - Otherwise, pick one of the overriders. Which one is used is unspecified,
//!   but remains the same throughtout the program, and across different runs of
//!   the same program.
struct n2216 {};

// -----------------------------------------------------------------------------
// trace

//! Enable `initialize` tracing.
//!
//! If `trace` is passed to @ref initialize, tracing code is added to various
//! parts of the initialization process (dispatch table construction, hash
//! factors search, etc). The tracing code is executed only if
//! @ref trace::on is set to `true`.
//!
//! `trace` requires the registry being initialized to have an @ref output
//! policy.
//!
//! The content of the trace is neither specified, nor stable across versions.
//! It is comprehensive, and useful for troubleshooting missing class
//! registrations, missing or ambiguous overriders, etc.
struct trace {
    //! Enable trace if `true`.
    bool on = true;

    trace(bool on = true) : on(on) {
    }

    //! Returns a `trace` object with `on` set to `true` if the environment
    //! variable `BOOST_OPENMETHOD_TRACE` is set to the string "1", and false
    //! otherwise.
    static trace from_env();
};

inline trace trace::from_env() {
#ifdef _MSC_VER
    char* env;
    std::size_t len;
    auto result = _dupenv_s(&env, &len, "BOOST_OPENMETHOD_TRACE") == 0 && env &&
        len == 2 && *env == '1';
    free(env);
    return trace(result);
#else
    auto env = getenv("BOOST_OPENMETHOD_TRACE");
    return trace(env && *env++ == '1' && *env++ == 0);
#endif
}

// =============================================================================
// policies

//! Namespace for policies.
//!
//! Classes with snake case names are "blueprints", i.e. exposition-only classes
//! that describe the requirements for policies of a given category. Classes
//! implementing these blueprints must provide a `fn<Registry>` metafunction
//! that conforms to the blueprint's requirements.
//!
//! @ref registry carries a complete explanation of registries and policies.
//!
//! @see @ref registry
//! @see [Registries and Policies](xref:ROOT:registries_and_policies.adoc)

namespace policies {

#ifdef __MRDOCS__

//! Class information for initializing a policy (exposition only).
//!
//! Provides the v-table pointer for a class, identified by one or more type
//! ids, via the members described on this page.
struct InitializeClass {
    //! Beginning of a range of type ids for a class.
    //!
    //! @return A forward iterator to the beginning of a range of type ids for
    //! a class.
    auto type_id_begin() const -> detail::unspecified;

    //! End of a range of type ids for a class.
    //!
    //! @return A forward iterator to the end of a range of type ids for a
    //! class.
    auto type_id_end() const -> detail::unspecified;

    //! Reference to the v-table pointer for the class.
    //!
    //! @return A reference to the v-table pointer for the class.
    auto vptr() const -> const vptr_type&;
};

//! Context for initializing a policy (exposition only).
//!
//! @ref initialize passes a "context" object, of unspecified type, to the
//! `initialize` functions of the policies that have one. It provides the
//! v-table pointer for the registered classes, via the members described on
//! this page.
struct InitializeContext {
    //! Beginning of a range of `InitializeClass` objects.
    //!
    //! @return A forward iterator to the beginning of a range of @ref
    //! InitializeClass objects.
    detail::unspecified classes_begin() const;

    //! End of a range of `InitializeClass` objects.
    //!
    //! @return A forward iterator to the end of a range of @ref
    //! InitializeClass objects.
    detail::unspecified classes_end() const;
};

//! Blueprint for @ref rtti metafunctions (exposition only).
template<class Registry>
struct RttiFn {
    //! Tests if a class is polymorphic.
    //!
    //! @tparam Class A class.
    template<class Class>
    static constexpr bool is_polymorphic = std::is_polymorphic_v<Class>;

    //! Returns the static @ref type_id of a type.
    //!
    //! @note `Class` is not necessarily a @e registered class. This
    //! function is also called to acquire the type_id of non-virtual
    //! parameters, library types, etc, for diagnostic and trace purposes.
    //!
    //! @tparam Class A class.
    //! @return The static type_id of Class.
    template<class Class>
    static auto static_type() -> type_id;

    //! Returns the dynamic @ref type_id of an object.
    //!
    //! @tparam Class A registered class.
    //! @param obj A reference to an instance of `Class`.
    //! @return The type_id of `obj`'s class.
    template<class Class>
    static auto dynamic_type(const Class& obj) -> type_id;

    //! Writes a representation of a @ref type_id to a stream.
    //!
    //! @tparam Stream A LightweightOutputStream.
    //! @param type The `type_id` to write.
    //! @param stream The stream to write to.
    template<typename Stream>
    static auto type_name(type_id type, Stream& stream);

    //! Returns a key that uniquely identifies a class.
    //!
    //! @param type A `type_id`.
    //! @return A unique value that identifies a class with the given
    //! `type_id`.
    static auto type_index(type_id type);

    //! Casts an object to a type.
    //!
    //! @tparam D A reference to a subclass of `B`.
    //! @tparam B A registered class.
    //! @param obj A reference to an instance of `B`.
    template<typename D, typename B>
    static auto dynamic_cast_ref(B&& obj) -> D;
};

#endif

// -----------------------------------------------------------------------------
// rtti

//! Policy for manipulating type information.
//!
//! `rtti` policies are responsible for type information acquisition and dynamic
//! casting.
//!
//! @par Requirements
//!
//! Classes implementing this policy must:
//! @li derive from @c rtti.
//! @li provide a @c fn<Registry> metafunction that conforms to the @ref RttiFn
//! blueprint.
//!
//! @see [Custom RTTI](xref:ROOT:custom_rtti.adoc)
struct rtti {
    // Policy category.
    using category = rtti;

    //! Default implementations of some `rtti` requirements.
    struct defaults {
        //! Default implementation for `type_index`.
        //!
        //! @param type A `type_id`.
        //!
        //! @return `type` itself.
        static auto type_index(type_id type) -> type_id {
            return type;
        }

        //! Default implementation of `type_name`.
        //!
        //! Executes `stream << "type_id(" << type << ")"`.
        //!
        //! @param type A `type_id`.
        //! @param stream A stream to write to.
        template<typename Stream>
        static void type_name(type_id type, Stream& stream) {
            stream << "type_id(" << type << ")";
        }
    };
};

// -----------------------------------------------------------------------------
// deferred rtti

//! Policy for deferred type id collection.
//!
//! Some custom RTTI systems rely on static constructors to assign type ids.
//! OpenMethod itself relies on static constructors to register classes, methods
//! and overriders. This creates order-of-initialization issues. Deriving a @e
//! rtti policy from this class - instead of just `rtti` - causes the collection
//! of type ids to be deferred until the first call to @ref update.
//!
//! @see [Custom RTTI](xref:ROOT:custom_rtti.adoc)
struct deferred_static_rtti : rtti {};

// -----------------------------------------------------------------------------
// error handler

#ifdef __MRDOCS__
//! Blueprint for @ref error_handler metafunctions (exposition only).
template<class Registry>
struct ErrorHandlerFn {
    //! Called when an error is detected.
    //!
    //! `error` is a function, or a set of functions, that can be called
    //! with an instance of any subclass of `openmethod_error`.
    static auto error(const auto& error) -> void;
};
#endif

//! Policy for error handling.
//!
//! A @e error_handler policy runs code before the library terminates the
//! program due to an error. This can be useful for throwing, logging, cleanup,
//! or other actions.
//!
//! @par Requirements
//!
//! Classes implementing this policy must:
//! @li derive from @c error_handler.
//! @li provide a @c fn<Registry> metafunction that conforms to the @ref
//! ErrorHandlerFn blueprint.
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct error_handler {
    // Policy category.
    using category = error_handler;
};

// -----------------------------------------------------------------------------
// vptr

#ifdef __MRDOCS__

//! Blueprint for `vptr` metafunctions (exposition only).
//!
//! @tparam Registry The registry containing the policy.
template<class Registry>
struct VptrFn {
    //! Register the v-table pointers.
    //!
    //! Called by @ref registry::initialize to let the policy store the v-table
    //! pointer associated to each `type_id`.
    //!
    //! @tparam Context A class that conforms to the @ref InitializeContext
    //! blueprint.
    //! @tparam Options... Zero or more option types, deduced from the
    //! function arguments.
    //! @param ctx A Context object.
    //! @param options A tuple of option objects.
    template<class Context, class... Options>
    static auto initialize(
        const Context& ctx, const std::tuple<Options...>& options) -> void;

    //! Return a *reference* to a v-table pointer for an object.
    //!
    //! @tparam Class A registered class.
    //! @param arg A reference to a const object of type `Class`.
    //! @return A reference to the v-table pointer for `Class`.
    template<class Class>
    static auto dynamic_vptr(const Class& arg) -> const vptr_type&;

    // Added by the `std::any` interop, under the name `type_vptr`. An `any`
    // knows the `type_id` of the value it contains, but has no object of that
    // type to hand to `dynamic_vptr`.

    //! Return a *reference* to the v-table pointer for a type.
    //!
    //! Return a reference to the v-table pointer that `initialize` associated
    //! to `type`.
    //!
    //! This function is optional. Implement it if the registry is to be used
    //! with virtual parameters whose `virtual_traits` supply a `type_id`
    //! themselves, instead of an object - see @ref VirtualTraits::vptr. Both
    //! @ref vptr_vector and @ref vptr_map provide it, and implement
    //! `dynamic_vptr` in terms of it.
    //!
    //! @param type A `type_id`.
    //! @return A reference to the v-table pointer for `type`.
    static auto vptr(type_id type) -> const vptr_type&;

    //! Release the resources allocated by `initialize`.
    //!
    //! This function is optional.
    //!
    //! @tparam Options... Zero or more option types, deduced from the
    //! function arguments.
    //! @param options A tuple of option objects.
    template<class... Options>
    static auto finalize(const std::tuple<Options...>& options) -> void;
};

#endif

//! Policy for v-table pointer acquisition.
//!
//! @par Requirements
//!
//! Classes implementing this policy must:
//! @li derive from @c vptr.
//! @li provide a @c fn<Registry> metafunction that conforms to the @ref
//! VptrFn blueprint.
//!
//! @see [Registries and Policies](xref:ROOT:registries_and_policies.adoc)
struct vptr {
    // Policy category.
    using category = vptr;
};

//! Policy to add an indirection to pointers to v-tables.
//!
//! If this policy is present, constructs like @ref virtual_ptr, @ref
//! inplace_vptr, @ref vptr_vector, etc use pointers to pointers to v-tables.
//! These indirect pointers remain valid after a call to @ref initialize, after
//! dynamically loading a library that adds classes, methods and overriders to
//! the registry.
//!
//! @see [Shared Libraries](xref:ROOT:shared_libraries.adoc)
struct indirect_vptr final {
    // Policy category.
    using category = indirect_vptr;
    template<class Registry>
    struct fn {};
};

// -----------------------------------------------------------------------------
// type_hash

#ifdef __MRDOCS__
//! Blueprint for @ref type_hash metafunctions (exposition only).
//!
//! @tparam Registry The registry containing the policy.
template<class Registry>
struct TypeHashFn {
    //! Initialize the hash table.
    //!
    //! @tparam Context A class that conforms to the @ref InitializeContext
    //! blueprint.
    //! @tparam Options... Zero or more option types, deduced from the
    //! function arguments.
    //! @param ctx A Context object.
    //! @param options A tuple of option objects.
    //!
    //! Use @ref hash_range to retrieve the minimum and maximum hash values
    //! after calling this function.
    template<class Context, class... Options>
    static auto initialize(
        const Context& ctx, const std::tuple<Options...>& options) -> void;

    //! Return the range of hash values produced by @ref hash.
    //!
    //! Only valid after a call to @ref initialize.
    //!
    //! @return A pair containing the minimum and maximum hash values.
    static auto hash_range() -> std::pair<std::size_t, std::size_t>;

    //! Hash a `type_id`.
    //!
    //! @param type A @ref type_id.
    //! @return A hash value for the given `type_id`.
    static auto hash(type_id type) -> std::size_t;

    //! Release the resources allocated by `initialize`.
    //!
    //! This function is optional.
    //!
    //! @tparam Options... Zero or more option types, deduced from the
    //! function arguments.
    //! @param options A tuple of option objects.
    template<class... Options>
    static auto finalize(const std::tuple<Options...>& options) -> void;
};
#endif

//! Policy for hashing type ids.
//!
//! @par Requirements
//!
//! Classes implementing this policy must:
//! @li derive from @c type_hash.
//! @li provide a @c fn<Registry> metafunction that conforms to the @ref
//! TypeHashFn blueprint.
//!
//! @see [Registries and Policies](xref:ROOT:registries_and_policies.adoc)
struct type_hash {
    // Policy category.
    using category = type_hash;
};

#ifdef __MRDOCS__

//! Blueprint for @ref output metafunctions (exposition only).
//!
//! @tparam Registry The registry containing the policy.
template<class Registry>
struct OutputFn {
    //! A @ref LightweightOutputStream.
    inline static LightweightOutputStream os;
};

#endif

// -----------------------------------------------------------------------------
// output

//! Policy for writing diagnostics and trace.
//!
//! If an `output` policy is present, the default error handler uses it to write
//! error messages to its output stream. @ref registry::initialize can also use
//! it to write trace messages.
//!
//! @par Requirements
//!
//! Classes implementing this policy must:
//! @li derive from @c output.
//! @li provide a @c fn<Registry> metafunction that conforms to the @ref
//! OutputFn blueprint.
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct output {
    // Policy category.
    using category = output;
};

// -----------------------------------------------------------------------------
// runtime_checks

//! Policy for post-initialize runtime checks.
//!
//! If this policy is present, performs the following checks:
//! @li Classes of virtual arguments have been registered.
//! @li Dynamic and static types match in "final" constructs (@ref
//! final_virtual_ptr and related functions).
//!
//! @see [Error Handling](xref:ROOT:error_handling.adoc)
struct runtime_checks final {
    // Policy category.
    using category = runtime_checks;
    template<class Registry>
    struct fn {};
};

} // namespace policies

// -----------------------------------------------------------------------------
// registry and policy helpers

namespace detail {

struct registry_base {};

// A minimal tuple. Unlike std::tuple (very expensive to instantiate with
// MSVC), it has no converting constructors, no comparisons, and no EBO
// machinery. It is used as a plain holder of heterogeneous objects
// (policy states, registrars), which are always default-constructed; `get`
// retrieves an element by type. Elements are held in base classes, so element
// types must be unique - lists that may contain duplicates are passed through
// mp_unique first.
//
// Measured (MSVC 19.51.36248, /Bt+ front-end time, synthetic
// BOOST_OPENMETHOD_CLASSES lists): ~11% less compile time at 40 classes
// (2.68s -> 2.39s, avg of 3 runs), ~7% at 100 classes (10.99s -> 10.22s).
// This is a constant-factor win that widens with list size, not a fix for
// superlinear blowups; on this library's own test suite (2-5 classes per
// list) the effect is within noise.
template<class T>
struct tuple_element {
    T element;
};

template<class... Ts>
struct tuple : tuple_element<Ts>... {};

template<class T, class... Ts>
auto get(tuple<Ts...>& t) -> T& {
    return static_cast<tuple_element<T>&>(t).element;
}

// Extracts ::state from T.
template<class T>
using policy_state_t = typename T::state;

// Detects whether T has a nested ::state type.
template<class T>
using has_policy_state = mp11::mp_valid<policy_state_t, T>;

// Quoted metafunction: maps a policy type P to P::template fn<Registry>.
template<class Registry>
struct policy_fn_q {
    template<class P>
    using fn = typename P::template fn<Registry>;
};

template<class Registry>
struct registry_state_type {
    static_list<class_info> classes;
    static_list<method_info> methods;
    bool initialized;
    std::vector<word> dispatch_data;
    // The per-policy `state` objects are held in a detail::tuple, whose
    // element types must be unique (each is a distinct base class). If two
    // stateful policies resolve to the same `state` type, raw instantiation
    // fails with a cryptic "duplicate base type ... invalid" pointing into
    // library internals. Diagnose it here instead. Do NOT mp_unique this
    // list to "fix" the error: that would silently alias the two policies
    // onto one shared state object.
    using policy_state_list = mp11::mp_transform<
        policy_state_t,
        mp11::mp_filter<
            has_policy_state,
            mp11::mp_transform_q<
                policy_fn_q<Registry>, typename Registry::policy_list>>>;
    static_assert(
        mp11::mp_size<policy_state_list>::value ==
            mp11::mp_size<mp11::mp_unique<policy_state_list>>::value,
        "two or more stateful policies in this registry share the same "
        "nested `state` type; each stateful policy must define its own "
        "distinct `state` type (give each its own nested struct)");
    using policies_type = mp11::mp_apply<detail::tuple, policy_state_list>;
    policies_type policies;
};

template<typename T>
constexpr bool is_registry = std::is_base_of_v<registry_base, T>;

template<typename T>
constexpr bool is_not_void = !std::is_same_v<T, void>;

template<class Base, class List, typename Default>
struct find_first_derived_of_aux;

template<class Base, class List, typename Default = void>
using find_first_derived_of =
    typename find_first_derived_of_aux<Base, List, Default>::type;

template<class Base, typename Default>
struct find_first_derived_of_aux<Base, mp11::mp_list<>, Default> {
    using type = Default;
};

template<class Base, typename Default, typename First, typename... More>
struct find_first_derived_of_aux<Base, mp11::mp_list<First, More...>, Default> {
    using type = std::conditional_t<
        std::is_base_of_v<Base, First>, First,
        find_first_derived_of<Base, mp11::mp_list<More...>, Default>>;
};

template<class Registry, class Policy>
struct get_policy_aux {
    using type = typename Policy::template fn<Registry>;
};

template<class Registry>
struct get_policy_aux<Registry, void> {
    using type = void;
};

template<class Policies, class...>
struct with_aux;

template<class Policies>
struct with_aux<Policies> {
    using type = Policies;
};

template<class Policies, class Policy, class... MorePolicies>
struct with_aux<Policies, Policy, MorePolicies...> {
    using replace = mp11::mp_replace_if_q<
        Policies,
        mp11::mp_bind_front_q<
            mp11::mp_quote_trait<std::is_base_of>, typename Policy::category>,
        Policy>;
    using replace_or_add = std::conditional_t<
        std::is_same_v<replace, Policies>, mp11::mp_push_back<Policies, Policy>,
        replace>;
    using type = typename with_aux<replace_or_add, MorePolicies...>::type;
};

template<class Policies, class...>
struct without_aux;

template<class Policies>
struct without_aux<Policies> {
    using type = Policies;
};

template<class Policies, class Policy, class... MorePolicies>
struct without_aux<Policies, Policy, MorePolicies...> {
    using type = typename without_aux<
        mp11::mp_remove_if_q<
            Policies,
            mp11::mp_bind_front_q<
                mp11::mp_quote_trait<std::is_base_of>,
                typename Policy::category>>,
        MorePolicies...>::type;
};

template<class...>
struct use_class_aux;

template<typename, class...>
struct initialize_aux;

} // namespace detail

#define BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN(FN)                              \
    template<typename, class, class...>                                        \
    struct BOOST_PP_CAT(has_, BOOST_PP_CAT(FN, _aux)) : std::false_type {};    \
    template<class T, class... Args>                                           \
    struct BOOST_PP_CAT(has_, BOOST_PP_CAT(FN, _aux))<                         \
        std::void_t<decltype(T::FN(std::declval<Args>()...))>, T, Args...>     \
        : std::true_type {};                                                   \
    template<class T, class... Args>                                           \
    constexpr bool BOOST_PP_CAT(has_, FN) =                                    \
        BOOST_PP_CAT(has_, BOOST_PP_CAT(FN, _aux))<void, T, Args...>::value

//! The single shared instance of a registry's state.
//!
//! `registry_state` is a thin, function-free class whose only member, `st`,
//! holds all of a registry's mutable state (of type @ref
//! detail::registry_state_type). Reach it through `Registry::state()`.
//!
//! It is deliberately a *separate* one-member class, rather than
//! `registry_state_type` itself, because sharing the state across a DLL
//! boundary on Windows requires exporting and importing a *whole class*:
//!
//! @li MSVC honors @c __declspec(dllexport/dllimport) on a class explicit
//!   instantiation, but NOT on a variable template (clients silently get a
//!   private copy) nor on a static-data-member instantiation (error C2720).
//!   So the exported symbol must be a class member reached via whole-class
//!   instantiation.
//! @li dllexporting @c registry_state_type directly would also decorate its
//!   member functions and, transitively, the policies' nested @c state types,
//!   which MSVC rejects (error C2513).
//!
//! A one-member, function-free class is the only shape MSVC will export as a
//! whole and import via `extern template`.
//!
//! To share the state across modules, use
//! @ref BOOST_OPENMETHOD_IMPORT_REGISTRY, @ref BOOST_OPENMETHOD_EXPORT_REGISTRY
//! and @ref BOOST_OPENMETHOD_INSTANTIATE_REGISTRY. They hide a platform
//! incompatibility: the export goes on the declaration on ELF and Mach-O, but
//! on the instantiation on declspec platforms, where `extern` and
//! `__declspec(dllexport)` cannot be combined.
//! @code
//! // header, every translation unit of a client module:
//! BOOST_OPENMETHOD_IMPORT_REGISTRY(boost::openmethod::default_registry);
//! // header, every translation unit of the owning module:
//! BOOST_OPENMETHOD_EXPORT_REGISTRY(boost::openmethod::default_registry);
//! // exactly one .cpp of the owning module:
//! BOOST_OPENMETHOD_INSTANTIATE_REGISTRY(boost::openmethod::default_registry);
//! @endcode
//!
//! @see [Shared Libraries](xref:ROOT:shared_libraries.adoc)
template<class Registry>
struct registry_state {
    static detail::registry_state_type<Registry> st;
};

template<class Registry>
detail::registry_state_type<Registry> registry_state<Registry>::st;

//! Methods, classes and policies.
//!
//! Methods exist in the context of a registry. Any class used as a method or
//! overrider parameter, or in as a method call argument, must be registered
//! with the same registry.
//!
//! Before calling a method, its registry must be initialized with the @ref
//! initialize function. This is typically done at the beginning of `main`.
//!
//! Multiple registries can co-exist in the same program. They must be
//! initialized individually. Classes referenced by methods in different
//! registries must be registered with each registry.
//!
//! A registry also contains a set of @ref policies that control how certain
//! operations are performed. For example, the `rtti` policy provides type
//! information, implements dynamic casting, etc. It can be replaced to
//! interface with custom RTII systems (like LLVM's).
//!
//! Policies are implemented as Boost.MP11 quoted metafunctions. A policy class
//! must contain a `fn<Registry>` template that provides a set of static
//! members, specific to the responsibility of the policy. Registries
//! instantiate policies by passing themselves to the nested `fn` class
//! templates.
//!
//! There are two reason for this design.
//!
//! Some policies are "stateful": they contain static _data_ members. Since
//! several registries can co-exist in the same program, each stateful policy
//! needs its own, separate set of static data members. For example, @ref
//! vptr_vector, a "vptr" policy, contains a static vector of vptrs, which
//! cannot be shared with other registries.
//!
//! Also, some policies need access to other policies in the same registry. They
//! can be accessed via the `Registry` template parameter. For example, @ref
//! vptr_vector hashes type_ids before using them as an indexes, if `Registry`
//! cotains a `type_hash` policy. It performs out-of-bounds checks if `Registry`
//! contains the `runtime_checks` policy. If an error is detected, it invokes
//! the @ref error_handler policy if there is  one.
//!
//! A registry is identified by its policy list, not by the class that derives
//! from it. Everything a registry owns is keyed on the `registry`
//! specialization, which is what @ref registry_type aliases. Two classes built
//! from the same policies, in the same order, are therefore the same registry:
//!
//! include:../examples/registry_identity.cpp#shared
//!
//! This matters when a second registry exists to isolate a set of methods from
//! another, since it would naturally be given the same policies. Give each one
//! a policy of its own to keep them apart:
//!
//! include:../examples/registry_identity.cpp#distinct
//!
//! @tparam Policy The policies used in the registry.
//!
//! @par Requirements
//!
//! @li @c Policy must contain a @c category alias to its root base class. The
//! registry may contain at most one policy per category.
//!
//! @li @c Policy must contain a @c fn<Registry> metafunction.
//!
//! @see @ref policies
//! @see [Registries and Policies](xref:ROOT:registries_and_policies.adoc)
template<class... Policy>
class registry : public detail::registry_base {

  public:
    //! List of policies selected in a registry.
    //!
    //! `policy_list` is a Boost.Mp11 list containing the policies passed to the
    //! @ref registry clas template.
    //!
    //! @tparam Class A registered class.
    using policy_list = mp11::mp_list<Policy...>;

    //! Find a policy by category.
    //!
    //! `policy` searches for a policy that derives from the specified @ref
    //! Category. If none is found, it aliases to `void`. Otherwise, it aliases
    //! to the policy's `fn` metafunction, applied to the registry.
    //!
    //! @tparam A policy.
    template<class Category>
    using policy = typename detail::get_policy_aux<
        registry, detail::find_first_derived_of<Category, policy_list>>::type;

  private:
    template<class...>
    friend struct detail::use_class_aux;
    template<typename Name, typename ReturnType, class Registry>
    friend class method;

    using static_ = registry_state<registry>;

  public:
    //! The type of this registry.
    //!
    //! `registry_type` is the `registry` specialization itself - for a
    //! registry defined as a struct deriving from `registry` (like @ref
    //! default_registry), the base class, not the struct. It is the type on
    //! which the registry's state is keyed. Two structs that derive from the
    //! same specialization therefore share one state, and are one registry;
    //! see @ref registry for how to keep two of them apart. It also appears in
    //! the explicit instantiation / `extern template` declaration pair that
    //! shares a custom registry's state across shared libraries:
    //! `registry_state<my_registry::registry_type>` (see @ref
    //! registry_state).
    using registry_type = registry;

    //! Return the registry's mutable state.
    //!
    //! Everything mutable in a registry - the class and method registration
    //! lists, the dispatch tables, and the state of every stateful policy -
    //! is agglomerated in a single variable,
    //! `registry_state<registry_type>::st`. `state` returns a reference to
    //! it.
    //!
    //! Modules (executables and shared libraries) contributing to the same
    //! registry must share this one variable; see @ref registry_state.
    static auto& state() {
        return static_::st;
    }

    //! Return a policy's state.
    //!
    //! Returns a reference to the `P::fn<registry_type>::state` object held
    //! in the registry's state. This is how stateful policies access their
    //! data members: policies do not keep their own global variables.
    //!
    //! @tparam P A stateful policy of this registry, i.e. one whose
    //! `fn<Registry>` contains a nested `state` type.
    template<class P>
    static auto& state() {
        return detail::get<typename P::template fn<registry>::state>(
            static_::st.policies);
    }

    //! Return an address identifying the registry's state.
    //!
    //! The address is the same in all the modules of a program if, and only
    //! if, they share the registry's state. Useful for diagnosing shared
    //! library setups.
    static const void* id() {
        return static_cast<const void*>(&static_::st.classes);
    }

    template<class... Options>
    struct compiler;

    //! Check that the registry is initialized.
    //!
    //! Check if `initialize` has been called for this registry, and report an
    //! error if not.
    //!
    //! @par Errors
    //!
    //! @li @ref not_initialized: The registry is not initialized.
    static void require_initialized();

    template<class... Options>
    static void finalize(Options... opts);

    //! A pointer to the virtual table for a registered class.
    //!
    //! `static_vptr` is set by @ref registry::initialize to the address of the
    //! class' virtual table. It remains valid until the next call to
    //! `initialize` or `finalize`.
    //!
    //! @tparam Class A registered class.
    template<class Class>
    inline static vptr_type static_vptr;

    //! Add or replace policies.
    //!
    //! `with` aliases to a registry with additional policies, overwriting any
    //! existing policies in the same category as the new ones.
    //!
    //! @tparam NewPolicies Models of @ref policies::Policy.
    template<class... NewPolicies>
    using with = boost::mp11::mp_apply<
        registry, typename detail::with_aux<policy_list, NewPolicies...>::type>;

    //! Remove policies.
    //!
    //! `without` aliases to a registry containing the same policies, except those
    //! that derive from `Categories`.
    //!
    //! @tparam Categories Models of @ref policies::PolicyCategory.
    template<class... Categories>
    using without = boost::mp11::mp_apply<
        registry,
        typename detail::without_aux<policy_list, Categories...>::type>;

    //! The registry's rtti policy.
    using rtti = policy<policies::rtti>;

    //! The registry's vptr policy if it contains one, or `void`.
    using vptr = policy<policies::vptr>;

    //! `true` if the registry has a vptr policy.
    static constexpr auto has_vptr = !std::is_same_v<vptr, void>;

    //! The registry's error_handler policy if it contains one, or `void`.
    using error_handler = policy<policies::error_handler>;

    //! `true` if the registry has an error_handler policy.
    static constexpr auto has_error_handler =
        !std::is_same_v<error_handler, void>;

    //! The registry's output policy if it contains one, or `void`.
    using output = policy<policies::output>;

    //! `true` if the registry has an output policy.
    static constexpr auto has_output = !std::is_same_v<output, void>;

    //! `true` if the registry has a deferred_static_rtti policy.
    static constexpr auto has_deferred_static_rtti =
        !std::is_same_v<policy<policies::deferred_static_rtti>, void>;

    //! `true` if the registry has a runtime_checks policy.
    static constexpr auto has_runtime_checks =
        !std::is_same_v<policy<policies::runtime_checks>, void>;

    //! `true` if the registry has an indirect_vptr policy.
    static constexpr auto has_indirect_vptr =
        !std::is_same_v<policy<policies::indirect_vptr>, void>;
};

template<class... Policies>
void registry<Policies...>::require_initialized() {
    if constexpr (registry::has_runtime_checks) {
        if (!static_::st.initialized) {
            if constexpr (registry::has_error_handler) {
                error_handler::error(not_initialized());
            }

            abort();
        }
    }
}

template<class Registry, class Stream>
auto missing_class::write(Stream& os) const {
    os << "unknown class ";
    Registry::rtti::type_name(type, os);
}

template<class Registry, class Stream>
auto missing_base::write(Stream& os) const {
    os << "missing base ";
    Registry::rtti::type_name(base, os);
    os << " -<| ";
    Registry::rtti::type_name(derived, os);
}

template<class Registry, class Stream>
auto final_error::write(Stream& os) const {
    os << "invalid call to final construct: static type = ";
    Registry::rtti::type_name(static_type, os);
    os << ", dynamic type = ";
    Registry::rtti::type_name(dynamic_type, os);
}

struct default_registry;
} // namespace boost::openmethod

#ifdef _MSC_VER
#pragma warning(pop)
#endif

#endif // BOOST_OPENMETHOD_REGISTRY_HPP
