// Copyright (c) 2017-2026 Jean-Louis Leroy
// Distributed under 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)

#ifndef BOOST_OPENMETHOD_COMPILER_HPP
#define BOOST_OPENMETHOD_COMPILER_HPP

#include <boost/openmethod/core.hpp>
#include <boost/openmethod/detail/ostdstream.hpp>

#include <algorithm>
#include <cstdint>
#include <deque>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include <boost/assert.hpp>
#include <boost/dynamic_bitset.hpp>

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4456)
#pragma warning(disable : 4458)
#pragma warning(disable : 4702) // unreachable code
#endif

namespace boost::openmethod {

namespace detail {

template<class Reports, class Facets, typename = void>
struct aggregate_reports;

template<class... Reports, class Facet, class... MoreFacets>
struct aggregate_reports<
    mp11::mp_list<Reports...>, mp11::mp_list<Facet, MoreFacets...>,
    std::void_t<typename Facet::report>> {
    using type = typename aggregate_reports<
        mp11::mp_list<Reports..., typename Facet::report>,
        mp11::mp_list<MoreFacets...>>::type;
};

template<class... Reports, class Facet, class... MoreFacets, typename Void>
struct aggregate_reports<
    mp11::mp_list<Reports...>, mp11::mp_list<Facet, MoreFacets...>, Void> {
    using type = typename aggregate_reports<
        mp11::mp_list<Reports...>, mp11::mp_list<MoreFacets...>>::type;
};

template<class... Reports, typename Void>
struct aggregate_reports<mp11::mp_list<Reports...>, mp11::mp_list<>, Void> {
    struct type : Reports... {};
};

// Policy initialization helpers

#ifdef BOOST_MSVC
#if BOOST_MSVC > 1951
#pragma message(                                                               \
    "boost/openmethod: this MSVC version is newer than 19.51, the last "       \
    "one confirmed to need the has_initialize/has_finalize SFINAE "            \
    "workaround below (wrong instantiation of the enclosing "                  \
    "boost::openmethod::initialize/finalize function templates during "        \
    "member-call SFINAE). Check whether this compiler still has the bug; "     \
    "if not, both workarounds (and this macro) can be removed.")
#endif
// `initialize` and `finalize` are also enclosing-namespace
// boost::openmethod::initialize/finalize function templates, so probing them
// with a call expression (the generic BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN
// form) is unsafe here: while evaluating decltype(T::FN(...)) for a T that
// has no such member, MSVC (19.44 and later, still present in 19.51) wrongly
// instantiates the body of the enclosing function template (for its auto
// return type), which re-enters this probe with new types - unbounded
// recursion. 19.44 stops with C1202/C7752; 19.51 exhausts all memory
// (C1060) instead. Take the address of a specialization instead: it only
// involves T's members.
#define BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN_MSVC_SAFE(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::template FN<std::decay_t<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
#else
#define BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN_MSVC_SAFE(FN)                    \
    BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN(FN)
#endif

BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN_MSVC_SAFE(initialize);

// Call initialize on a single policy if it has the function
template<typename Policy, typename Registry, typename Context, typename Options>
void initialize_policy(const Context& ctx, const Options& options) {
    using PolicyFn = typename Policy::template fn<Registry>;
    if constexpr (has_initialize<PolicyFn, const Context&, const Options&>) {
        PolicyFn::initialize(ctx, options);
    }
}

template<typename Registry, typename Policies = typename Registry::policy_list>
struct initialize_policies;

template<typename Registry, typename... Policies>
struct initialize_policies<Registry, mp11::mp_list<Policies...>> {
    template<typename Context, typename Options>
    static void fn(const Context& ctx, const Options& options) {
        // Policies are initialized in `policy_list` order (left to right). A
        // policy that depends on another policy having been initialized (e.g.
        // vptr_vector reading a type_hash policy's state) must therefore appear
        // *after* its dependency in the list. finalize() runs in reverse order.
        (initialize_policy<Policies, Registry>(ctx, options), ...);
    }
};

// Saves the policies' states on construction, and puts them back on
// destruction unless commit() was called - so a policy's `initialize` that
// throws, after itself or another policy has already written to shared
// state, leaves the registry as it was. The registry's mutable state is one
// variable, registry_state<Registry>::st; its `policies` tuple is copied
// whole, states of policies without an `initialize` included, since
// restoring an untouched state is harmless, and simpler than picking. The
// other members need no saving: initialize() only reads the class and
// method lists, and write_global_data() replaces dispatch_data at commit
// time only, after which nothing can throw - on rollback it still holds the
// previous tables, which the classes' static_vptrs point into. (That is
// also why a copy could not stand in for it: it would be another buffer.)
template<class Registry>
class registry_state_transaction {
  public:
    registry_state_transaction() : saved(Registry::state().policies) {
    }

    ~registry_state_transaction() {
        if (!committed) {
            Registry::state().policies = std::move(saved);
        }
    }

    registry_state_transaction(const registry_state_transaction&) = delete;
    auto operator=(const registry_state_transaction&)
        -> registry_state_transaction& = delete;

    void commit() {
        committed = true;
    }

  private:
    typename registry_state_type<Registry>::policies_type saved;
    bool committed = false;
};

inline void merge_into(boost::dynamic_bitset<>& a, boost::dynamic_bitset<>& b) {
    if (b.size() < a.size()) {
        b.resize(a.size());
    }

    for (std::size_t i = 0; i < a.size(); ++i) {
        if (a[i]) {
            b[i] = true;
        }
    }
}

inline void set_bit(boost::dynamic_bitset<>& mask, std::size_t bit) {
    if (bit >= mask.size()) {
        mask.resize(bit + 1);
    }

    mask[bit] = true;
}

inline auto is_free(
    const boost::dynamic_bitset<>& unavailable, std::size_t slot) -> bool {
    return slot >= unavailable.size() || !unavailable[slot];
}

struct generic_compiler {

    struct method;

    struct parameter {
        struct method* method;
        std::size_t param;
    };

    struct vtbl_entry {
        std::size_t method_index, vp_index, group_index;
    };

    struct class_ {
        std::vector<detail::class_info*> ci;
        // What the records declared, before the closure is computed; emptied by
        // calculate_transitive_bases.
        std::vector<class_*> declared_bases;
        std::vector<class_*> transitive_bases;
        std::vector<class_*> direct_bases;
        std::vector<class_*> direct_derived;
        std::unordered_set<class_*> transitive_derived;
        std::vector<parameter> used_by_vp;
        // The slots occupied in this class's v-table: those of every parameter
        // allocated so far on the class or on any of its ancestors. Grows only
        // through `set_bit` and `merge_into`, so `size()` is one past the
        // highest slot.
        boost::dynamic_bitset<> used_slots;
        std::size_t first_slot = 0;
        std::size_t mark = 0; // temporary mark to detect cycles
        bool transitive_bases_done = false;
        std::vector<vtbl_entry> vtbl;
        // The v-table pointer initialize() is about to install for the class.
        // Staged here by write_global_data(), where the policies read it (see
        // class_view); written to the class_infos' static_vptr only once
        // everything that can fail has succeeded.
        vptr_type vptr = nullptr;

        auto is_base_of(class_* other) const -> bool {
            return transitive_derived.find(other) != transitive_derived.end();
        }

        auto is_abstract() const -> bool {
            return ci[0]->is_abstract;
        }
    };

    struct slot_choice {
        std::size_t slot, cost;
    };

    template<class Classes>
    static auto pick_slot(
        const Classes& cone, const boost::dynamic_bitset<>& unavailable)
        -> slot_choice;

    struct overrider {
        detail::overrider_info* info = nullptr;
        overrider* next = nullptr;
        std::vector<class_*> vp;
        class_* covariant_return_type = nullptr;
        void (*pf)();
        std::size_t method_index, spec_index;
    };

    using bitvec = boost::dynamic_bitset<>;

    struct group {
        std::vector<class_*> classes;
        bool has_concrete_classes{false};
    };

    using group_map = std::map<bitvec, group>;

    struct method_report {
        std::size_t cells = 0;
        std::size_t not_implemented = 0;
        std::size_t ambiguous = 0;
    };

    struct report : method_report {};

    static void accumulate(const method_report& partial, report& total);

    struct method {
        std::size_t index;
        // All method_info instances for this logical method, one per module
        // that instantiated the method's `fn`. `info` is one of these. Used to
        // propagate slots_strides to every copy after the dispatch table is
        // built.
        std::vector<detail::method_info*> infos;
        std::vector<class_*> vp;
        class_* covariant_return_type = nullptr;
        std::vector<overrider> overriders;
        std::vector<std::size_t> slots;
        std::vector<std::size_t> strides;
        std::vector<const overrider*> dispatch_table;
        // following two are dummies, when converting to a function pointer, we will
        // get the corresponding pointer from method_info
        overrider not_implemented;
        overrider ambiguous;
        vptr_type gv_dispatch_table = nullptr;
        auto arity() const {
            return vp.size();
        }
        method_report report;
    };

    const method* operator[](const detail::method_info& info) const {
        auto iter = std::find_if(
            methods.begin(), methods.end(), [&info](const method& m) {
                return std::find(m.infos.begin(), m.infos.end(), &info) !=
                    m.infos.end();
            });

        if (iter != methods.end()) {
            return &*iter;
        }

        return nullptr;
    }

    std::deque<class_> classes;

    // What a policy's `initialize` sees for each class (the InitializeClass
    // blueprint): the type ids of one class_info, and the v-table pointer
    // that initialize() is about to install for the class. `vptr()` is the
    // value staged in the class_, not what the class_info's static_vptr
    // holds - that is still the previous v-table, and stays so until every
    // policy has succeeded. `static_vptr()` is the address that will receive
    // it, for the policies that store pointers to v-table pointers
    // (indirect_vptr): the one thing here that is stable across
    // re-initializations.
    struct class_view {
        const detail::class_info* ci;
        const class_* cls;

        auto type_id_begin() const {
            return ci->type_id_begin();
        }

        auto type_id_end() const {
            return ci->type_id_end();
        }

        auto vptr() const -> vptr_type {
            return cls->vptr;
        }

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

    class const_class_iterator {
      public:
        // The view is made on the fly, so `operator->` has nothing to point
        // at; it returns one of these, which points at the view it carries.
        // The proxy lives until the end of the full expression, which is as
        // long as a policy needs it: `vptr()` and `static_vptr()` return
        // values.
        struct arrow_proxy {
            class_view view;

            auto operator->() const -> const class_view* {
                return &view;
            }
        };

        using iterator_category = std::forward_iterator_tag;
        using value_type = class_view;
        using difference_type = std::ptrdiff_t;
        using pointer = arrow_proxy;
        using reference = class_view;

        const_class_iterator() = default;

        const_class_iterator(
            std::deque<class_>::const_iterator class_iter,
            std::deque<class_>::const_iterator class_end) :
            class_iter_(class_iter), class_end_(class_end) {
            if (class_iter_ != class_end_) {
                ci_iter_ = class_iter_->ci.begin();
                advance_to_valid();
            }
        }
        auto operator*() const -> class_view {
            return {*ci_iter_, &*class_iter_};
        }

        auto operator->() const -> arrow_proxy {
            return {**this};
        }

        auto operator++() -> const_class_iterator& {
            ++ci_iter_;
            advance_to_valid();
            return *this;
        }

        auto operator++(int) -> const_class_iterator {
            const_class_iterator tmp = *this;
            ++(*this);
            return tmp;
        }

        auto operator==(const const_class_iterator& other) const -> bool {
            if (class_iter_ != other.class_iter_) {
                return false;
            }
            if (class_iter_ == class_end_) {
                return true;
            }
            return ci_iter_ == other.ci_iter_;
        }

        auto operator!=(const const_class_iterator& other) const -> bool {
            return !(*this == other);
        }

      private:
        void advance_to_valid() {
            while (class_iter_ != class_end_ &&
                   ci_iter_ == class_iter_->ci.end()) {
                ++class_iter_;
                if (class_iter_ != class_end_) {
                    ci_iter_ = class_iter_->ci.begin();
                }
            }
        }

        std::deque<class_>::const_iterator class_iter_;
        std::deque<class_>::const_iterator class_end_;
        std::vector<detail::class_info*>::const_iterator ci_iter_;
    };

    auto classes_begin() const {
        return const_class_iterator(classes.begin(), classes.end());
    }

    auto classes_end() const {
        return const_class_iterator(classes.end(), classes.end());
    }

    std::deque<method> methods;
    std::size_t class_mark = 0;
    bool compilation_done = false;
};

// Choose the slot for a new parameter of a class. `cone` holds the class and
// every class deriving from it; `unavailable` is the union of their
// `used_slots`. The cost of a slot is the number of entries it adds to the
// cone's v-tables: none inside a v-table's range (a hole gets filled), one per
// slot of growth beyond either end, one for a class that has no v-table yet.
// The cheapest free slot wins, the lowest on ties.
//
// Each v-table contributes a cost that is flat inside its range and grows by
// one per slot away from it, so the sum is swept from slot 0 upwards: moving
// to the next slot adds one per range already ended and removes one per range
// not yet started.
template<class Classes>
auto generic_compiler::pick_slot(
    const Classes& cone, const boost::dynamic_bitset<>& unavailable)
    -> slot_choice {
    // Slot `slots` is beyond every v-table, hence always free.
    const auto slots = unavailable.size();
    std::vector<std::size_t> starting_at(slots), ending_at(slots);
    std::size_t ranges = 0, cost = 0;

    for (auto cls : cone) {
        const auto& used = cls->used_slots;

        if (used.empty()) {
            // A one-entry v-table, wherever the slot lands.
            ++cost;
            continue;
        }

        auto first = used.find_first();
        BOOST_ASSERT(first != boost::dynamic_bitset<>::npos);
        BOOST_ASSERT(used.size() <= slots);
        ++starting_at[first];
        ++ending_at[used.size() - 1];
        ++ranges;
        cost += first; // the distance from slot 0
    }

    slot_choice best{0, std::numeric_limits<std::size_t>::max()};
    std::size_t started = 0, ended = 0;

    for (std::size_t slot = 0;; ++slot) {
        if (is_free(unavailable, slot) && cost < best.cost) {
            best = {slot, cost};
        }

        if (slot == slots) {
            return best;
        }

        started += starting_at[slot];
        ended += ending_at[slot];
        cost = cost + ended - (ranges - started);
    }
}

template<class Compiler>
struct trace_stream {
    bool on = false;
    std::size_t indentation_level{0};

    auto operator++() -> trace_stream& {
        if constexpr (Compiler::has_trace) {
            if (on) {
                for (std::size_t i = 0; i < indentation_level; ++i) {
                    Compiler::Registry::output::stream() << "  ";
                }
            }
        }

        return *this;
    }

    struct indent {
        trace_stream& trace;
        int by;

        explicit indent(trace_stream& trace, int by = 2) :
            trace(trace), by(by) {
            trace.indentation_level += by;
        }

        ~indent() {
            trace.indentation_level -= by;
        }
    };
};

struct rflush {
    std::size_t width;
    std::size_t value;
    explicit rflush(std::size_t width, std::size_t value) :
        width(width), value(value) {
    }
};

struct type_name {
    type_name(type_id type) : type(type) {
    }
    type_id type;
};

template<class Compiler>
auto operator<<(trace_stream<Compiler>& tr, const generic_compiler::class_& cls)
    -> trace_stream<Compiler>& {
    if constexpr (Compiler::has_trace) {
        tr << type_name(cls.ci[0]->type);
    }

    return tr;
}

template<class Compiler, template<typename...> class Container, typename... T>
auto operator<<(
    trace_stream<Compiler>& tr,
    Container<generic_compiler::class_*, T...>& classes)
    -> trace_stream<Compiler>& {
    if constexpr (Compiler::has_trace) {
        tr << "(";
        const char* sep = "";
        for (auto cls : classes) {
            tr << sep << *cls;
            sep = ", ";
        }

        tr << ")";
    }

    return tr;
}

struct spec_name {
    spec_name(
        const detail::generic_compiler::method& method,
        const detail::generic_compiler::overrider* def) :
        method(method), def(def) {
    }
    const detail::generic_compiler::method& method;
    const detail::generic_compiler::overrider* def;
};

template<class Compiler>
auto operator<<(trace_stream<Compiler>& tr, const spec_name& sn)
    -> trace_stream<Compiler>& {
    if (sn.def == &sn.method.not_implemented) {
        tr << "not implemented";
    } else if (sn.def == &sn.method.ambiguous) {
        tr << "ambiguous";
    } else {
        tr << type_name(sn.def->info->type);
    }

    return tr;
}

template<typename Iterator>
struct range {
    range(Iterator first, Iterator last) : first(first), last(last) {
    }

    Iterator first, last;

    auto begin() const -> Iterator {
        return first;
    }

    auto end() const -> Iterator {
        return last;
    }
};

template<class Compiler, typename T, typename F>
auto write_range(trace_stream<Compiler>& tr, range<T> range, F fn) -> auto& {
    if constexpr (Compiler::has_trace) {
        if (tr.on) {
            tr << "(";
            const char* sep = "";
            for (auto value : range) {
                tr << sep << fn(value);
                sep = ", ";
            }

            tr << ")";
        }
    }

    return tr;
}

template<class Compiler, typename T>
auto operator<<(trace_stream<Compiler>& tr, const T& value) -> auto& {
    if constexpr (Compiler::has_trace) {
        if (tr.on) {
            Compiler::Registry::output::stream() << value;
        }
    }
    return tr;
}

template<class Compiler>
auto operator<<(trace_stream<Compiler>& tr, const rflush& rf) -> auto& {
    if constexpr (Compiler::has_trace) {
        if (tr.on) {
            std::size_t digits = 1;
            auto tmp = rf.value / 10;

            while (tmp) {
                ++digits;
                tmp /= 10;
            }

            while (digits < rf.width) {
                tr << " ";
                ++digits;
            }

            tr << rf.value;
        }
    }

    return tr;
}

template<class Compiler>
auto operator<<(trace_stream<Compiler>& tr, const boost::dynamic_bitset<>& bits)
    -> auto& {
    if constexpr (Compiler::has_trace) {
        if (tr.on) {
            auto i = bits.size();
            while (i != 0) {
                --i;
                Compiler::Registry::output::stream() << bits[i];
            }
        }
    }

    return tr;
}

template<class Compiler>
auto operator<<(trace_stream<Compiler>& tr, const range<type_id*>& tips)
    -> auto& {
    return write_range(tr, tips, [](auto tip) { return type_name(tip); });
}

template<class Compiler, typename T>
auto operator<<(trace_stream<Compiler>& tr, const range<T>& range) -> auto& {
    return write_range(tr, range, [](auto value) { return value; });
}

template<class Compiler>
auto operator<<(trace_stream<Compiler>& tr, const type_name& manip) -> auto& {
    if constexpr (Compiler::has_trace) {
        Compiler::Registry::rtti::type_name(manip.type, tr);
    }

    return tr;
}
} // namespace detail

// Definition of the nested template struct outside the registry class
template<class... Policies>
template<class... Options>
struct registry<Policies...>::compiler : detail::generic_compiler {
    using type_index_type = decltype(rtti::type_index(0));

    typename detail::aggregate_reports<mp11::mp_list<report>, policy_list>::type
        report;

    std::unordered_map<type_index_type, class_*> class_map;

    using Registry = registry;

    compiler(Options... opts);

    auto compile();
    void initialize();
    void install_global_tables();

    void augment_classes();
    void calculate_transitive_bases(class_& cls);
    void calculate_transitive_derived(class_& cls);
    void augment_methods();
    void assign_slots();
    void assign_tree_slots(class_& cls, std::size_t base_slot);
    void assign_slots(class_& cls);
    void build_dispatch_tables();
    void build_dispatch_table(
        method& m, std::size_t dim,
        std::vector<group_map>::const_iterator group, const bitvec& candidates,
        bool concrete);
    void write_global_data();
    void print(const method_report& report) const;
    void print_slots();
    static void select_dominant_overriders(
        std::vector<overrider*>& dominants, std::size_t& pick,
        std::size_t& remaining);
    static auto is_more_specific(const overrider* a, const overrider* b)
        -> bool;
    static auto is_base(const overrider* a, const overrider* b) -> bool;

    std::tuple<Options...> options;

    template<class Option>
    static constexpr bool has_option =
        mp11::mp_contains<mp11::mp_list<Options...>, Option>::value;

    static constexpr bool has_trace = has_option<trace>;
    static constexpr bool has_n2216 = has_option<n2216>;

    mutable detail::trace_stream<compiler> tr;
    using indent = typename detail::trace_stream<compiler>::indent;
};

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::install_global_tables() {
    if (!compilation_done) {
        abort();
    }

    write_global_data();

    print(report);
    print_slots();
    ++tr << "Finished\n";
}

template<class... Policies>
template<class... Options>
auto registry<Policies...>::compiler<Options...>::compile() {
    augment_classes();
    augment_methods();
    assign_slots();
    build_dispatch_tables();

    compilation_done = true;

    return report;
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::initialize() {
    // Clear the flag up front, and set it only once everything has succeeded.
    // A run that throws leaves the previous dispatch state in place, complete
    // and consistent (see write_global_data()) - but not marked initialized:
    // those tables do not reflect the registrations that prompted the call,
    // and after a dlclose (the documented re-initialize flow) they may point
    // into unloaded code, so require_initialized() must keep refusing to
    // dispatch until an initialize() succeeds.
    registry<Policies...>::static_::st.initialized = false;
    compile();
    install_global_tables();
    registry<Policies...>::static_::st.initialized = true;
}

#ifdef _MSC_VER
namespace detail {

template<bool HasTrace, typename T>
struct msvc_tuple_get;

template<typename T>
struct msvc_tuple_get<true, T> {
    template<class Tuple>
    static decltype(auto) fn(const Tuple& t) {
        return std::get<T>(t);
    }
};

template<typename T>
struct msvc_tuple_get<false, T> {
    template<class Tuple>
    static decltype(auto) fn(const Tuple&) {
        return T();
    }
};
} // namespace detail
#endif

template<class... Policies>
template<class... Options>
registry<Policies...>::compiler<Options...>::compiler(Options... opts) :
    options(opts...) {
    if constexpr (has_trace) {
#ifdef _MSC_VER
        tr.on = detail::msvc_tuple_get<has_trace, trace>::fn(options).on;
#else
        // Even with the constexpr has_trace guard, msvc errors on this.
        tr.on = std::get<trace>(options).on;
#endif
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::calculate_transitive_bases(
    class_& cls) {
    if (cls.transitive_bases_done) {
        return;
    }

    // Set before recursing. Inheritance cannot cycle, so this only guards
    // against a malformed set of records.
    cls.transitive_bases_done = true;

    // Complete every declared base first, so that merging them below sees
    // their full closure. Recursing bumps `class_mark`, hence the fresh mark
    // afterwards.
    for (auto base : cls.declared_bases) {
        calculate_transitive_bases(*base);
    }

    auto mark = ++class_mark;

    for (auto base : cls.declared_bases) {
        if (base->mark != mark) {
            base->mark = mark;
            cls.transitive_bases.push_back(base);
        }

        for (auto base_base : base->transitive_bases) {
            if (base_base->mark != mark) {
                base_base->mark = mark;
                cls.transitive_bases.push_back(base_base);
            }
        }
    }

    cls.declared_bases.clear();
    cls.declared_bases.shrink_to_fit();
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::augment_classes() {
    using namespace detail;

    // scope
    {
        ++tr << "Static class info:\n";

        // The standard does not guarantee that there is exactly one
        // type_info object per class. However, it guarantees that the
        // type_index for a class has a unique value.
        for (auto& cr : registry::static_::st.classes) {
            if constexpr (has_deferred_static_rtti) {
                static_cast<deferred_class_info&>(cr).resolve_type_ids();
            }

            {
                indent _(tr);
                ++tr << type_name(cr.type) << ": "
                     << range{cr.first_base, cr.last_base}
                     << ", type = " << cr.type << ", &vptr = " << &cr.vptr()
                     << "\n";
            }

            auto& rtc = class_map[rtti::type_index(cr.type)];

            if (rtc == nullptr) {
                rtc = &classes.emplace_back();
            }

            // Retain one class_info per (type, static_vptr) pair, not per
            // type. Under hidden visibility a class' type_id can unify
            // across modules while Registry::static_vptr<Class> does not
            // (each module has its own COMDAT copy), so the shared class
            // list legitimately holds several class_info entries for the
            // same class. write_global_data() patches every retained
            // entry's static_vptr; dropping the extras on type alone would
            // leave other modules' static_vptr null. Two entries are true
            // duplicates only when writing through either has the same
            // effect.
            bool duplicate = false;

            for (auto ci : rtc->ci) {
                if (rtti::type_index(ci->type) == rtti::type_index(cr.type) &&
                    ci->static_vptr == cr.static_vptr) {
                    duplicate = true;
                    break;
                }
            }

            if (!duplicate) {
                rtc->ci.push_back(&cr);
            }
        }
    }

    // All known classes now have exactly one associated class_* in the
    // map. Collect the bases.

    for (auto& cr : registry::static_::st.classes) {
        auto rtc = class_map[rtti::type_index(cr.type)];

        for (auto& base : range{cr.first_base, cr.last_base}) {
            auto rtb = class_map[rtti::type_index(base)];

            if (!rtb) {
                missing_class error;
                error.type = base;

                if constexpr (has_error_handler) {
                    error_handler::error(error);
                }

                abort();
            }

            if (rtc != rtb) {
                // At compile time we collected the class as its own
                // improper base, as per std::is_base_of. Eliminate that.
                rtc->declared_bases.push_back(rtb);
            }
        }
    }

    // `declared_bases` now holds whatever the records said - direct bases,
    // ancestors, or a mixture, with duplicates. Turn that into the transitive
    // closure. This is done here rather than while reading the records because
    // a record's bases are only as informative as the records already seen: a
    // class registered before its own bases would otherwise be left with a
    // short list. That matters beyond `transitive_bases` itself, because the
    // direct-base derivation below sorts on its size.

    for (auto& rtc : classes) {
        calculate_transitive_bases(rtc);
    }

    for (auto& rtc : classes) {
        // Sort base classes by number of transitive bases. This ensures that a
        // base class is never preceded by one if its own base classes.
        std::sort(
            rtc.transitive_bases.begin(), rtc.transitive_bases.end(),
            [](auto a, auto b) {
                return a->transitive_bases.size() > b->transitive_bases.size();
            });
        auto mark = ++class_mark;

        // Collect the direct base classes. The first base is certainly a
        // direct one. Remove *its* bases from the candidates, by marking
        // them. Continue with the next base that is not marked. It is the
        // next direct base. And so on...

        for (auto rtb : rtc.transitive_bases) {
            if (rtb->mark == mark) {
                continue;
            }

            rtc.direct_bases.push_back(rtb);

            for (auto rtbb : rtb->transitive_bases) {
                rtbb->mark = mark;
            }
        }
    }

    for (auto& rtc : classes) {
        for (auto rtb : rtc.direct_bases) {
            rtb->direct_derived.push_back(&rtc);
        }
    }

    for (auto& rtc : classes) {
        calculate_transitive_derived(rtc);
    }

    if constexpr (has_trace) {
        ++tr << "Inheritance lattice:\n";

        for (auto& rtc : classes) {
            indent _2(tr);
            ++tr << rtc << "\n";

            {
                indent _3(tr);
                ++tr << "bases:      " << rtc.direct_bases << "\n";
                ++tr << "derived:    " << rtc.direct_derived << "\n";
                ++tr << "covariant:  " << rtc.transitive_derived << "\n";
            }
        }
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::calculate_transitive_derived(
    class_& cls) {
    if (!cls.transitive_derived.empty()) {
        return;
    }

    cls.transitive_derived.insert(&cls);

    for (auto derived : cls.direct_derived) {
        if (derived->transitive_derived.empty()) {
            calculate_transitive_derived(*derived);
        }

        std::copy(
            derived->transitive_derived.begin(),
            derived->transitive_derived.end(),
            std::inserter(
                cls.transitive_derived, cls.transitive_derived.end()));
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::augment_methods() {
    using namespace policies;
    using namespace detail;

    // Resolve deferred type ids first so consolidation keys are correct.
    // Overriders must be resolved here too (not only in the per-overrider
    // loop below) because the cross-module overrider dedup key uses their
    // type ids.
    if constexpr (has_deferred_static_rtti) {
        for (auto& meth_info : registry::static_::st.methods) {
            static_cast<deferred_method_info&>(meth_info).resolve_type_ids();
            for (auto& spec : meth_info.overriders) {
                static_cast<deferred_overrider_info&>(spec).resolve_type_ids();
            }
        }
    }

    // Group method copies across modules (DLL boundaries) by type_index.
    // The "local" entry is the first one we encounter — the method_info that
    // lives in the module performing initialize(). It owns the compiler's
    // working state for that method; the others get their slots_strides
    // copied from it later.
    std::map<type_index_type, method*> method_map;

    for (auto& info : registry::static_::st.methods) {
        auto key = rtti::type_index(info.method_type_id);
        auto [iter, inserted] = method_map.try_emplace(key, nullptr);

        if (inserted) {
            methods.emplace_back();
            iter->second = &methods.back();
        }

        iter->second->infos.push_back(&info);
    }

    std::size_t method_index = 0;

    ++tr << "Methods:\n";
    indent _(tr);

    for (auto& method : methods) {
        method.index = method_index++;
        auto first_info = method.infos[0];
        BOOST_ASSERT(first_info);
        // Every info in method.infos was grouped here because it shares the
        // same method_type_id (see method_map above). Under a well-behaved
        // RTTI policy that key is injective per method, so all of them
        // describe the very same method and must agree on arity. A custom
        // RTTI policy that returns a shared sentinel id for unregistered
        // types (e.g. a fixed value for every non-polymorphic type) can
        // break that assumption and silently merge distinct methods; catch
        // it here instead of corrupting slots_strides downstream.
        for (auto info : method.infos) {
            (void)info; // unused when BOOST_ASSERT compiles out (NDEBUG)
            BOOST_ASSERT(info->arity() == first_info->arity());
        }
        method.vp.reserve(first_info->arity());
        method.slots.resize(first_info->arity());

        ++tr << type_name(first_info->method_type_id) << " "
             << range{first_info->vp_begin, first_info->vp_end} << "\n";
        indent _(tr);

        // Build the virtual-parameter classes once, from the local
        // method_info. All copies describe the same method, so any one of them
        // yields the same vp list.
        {
            std::size_t param_index = 0;

            for (auto ti : range{first_info->vp_begin, first_info->vp_end}) {
                auto class_ = class_map[rtti::type_index(ti)];
                if (!class_) {
                    ++tr << "unknown class " << ti << "(" << type_name(ti)
                         << ") for parameter #" << (param_index + 1) << "\n";
                    missing_class error;
                    error.type = ti;

                    if constexpr (has_error_handler) {
                        error_handler::error(error);
                    }

                    abort();
                }

                method.vp.push_back(class_);
                ++param_index;
            }
        }

        if (rtti::type_index(first_info->return_type_id) !=
            rtti::type_index(rtti::template static_type<void>())) {
            auto covariant_return_iter =
                class_map.find(rtti::type_index(first_info->return_type_id));

            if (covariant_return_iter != class_map.end()) {
                method.covariant_return_type = covariant_return_iter->second;
            }
        }

        // Collect overriders from every module copy of this method, deduping
        // by *logical* identity rather than pointer identity - but only for
        // overriders declared inline_. The same overrider, defined in a
        // header and registered by two or more state-sharing modules (e.g.
        // an exe and a DLL), appears once per module as a distinct
        // overrider_info object - different address, and a different `pf`
        // (each module compiles its own copy of the function) - but they
        // share the same function type id and the same virtual-parameter
        // type ids. Keeping every copy would make each dispatch cell they
        // fill ambiguous, because is_more_specific() reports "not more
        // specific" both ways for identical vp lists.
        //
        // A NON-inline overrider with the same signature must never be
        // merged, even if it happens to match: BOOST_OPENMETHOD_OVERRIDE
        // (non-inline) keys one explicit specialization per signature, so
        // writing it twice in one translation unit is a redefinition error,
        // and defining it identically in more than one TU (as required for
        // it to appear "duplicated" in the first place) is an ODR violation
        // for a non-inline function - i.e. the situation this dedup exists
        // to handle can only arise legitimately for `inline` overriders (see
        // BOOST_OPENMETHOD_INLINE_OVERRIDE, which is the only thing that
        // sets overrider_info::inline_ = true). Two DIFFERENT overriders
        // sharing a signature (e.g. registered directly via
        // method<...>::override<Fn1> and method<...>::override<Fn2>, both
        // non-inline by default) are always genuinely distinct and must
        // remain ambiguous.
        std::vector<detail::overrider_info*> all_specs;
        std::size_t module_index = 0;

        for (auto info : method.infos) {
            indent _(tr);
            ++tr << "module " << module_index++ << "\n";

            for (auto& spec : info->overriders) {
                auto same = [&](const detail::overrider_info* kept) {
                    if (!kept->inline_ || !spec.inline_) {
                        return false;
                    }

                    if (rtti::type_index(kept->type) !=
                        rtti::type_index(spec.type)) {
                        return false;
                    }

                    // Same function type id: confirm the virtual-parameter
                    // signatures match too, so two genuinely different
                    // overriders that happen to share a function type id are
                    // never merged.
                    auto a = kept->vp_begin, ae = kept->vp_end,
                         b = spec.vp_begin;

                    for (; a != ae; ++a, ++b) {
                        if (rtti::type_index(*a) != rtti::type_index(*b)) {
                            return false;
                        }
                    }

                    return true;
                };

                if (std::none_of(all_specs.begin(), all_specs.end(), same)) {
                    all_specs.push_back(&spec);
                }
            }
        }

        // initialize the function pointer in the synthetic not_implemented
        // overrider
        auto spec_size = all_specs.size();
        method.not_implemented.pf = first_info->not_implemented;
        method.not_implemented.method_index = method.index;
        method.not_implemented.spec_index = spec_size;
        method.ambiguous.pf = first_info->ambiguous;
        method.ambiguous.method_index = method.index;
        method.ambiguous.spec_index = spec_size + 1;

        method.overriders.resize(spec_size);
        auto spec_iter = method.overriders.begin();

        for (auto overrider_info : all_specs) {
            if constexpr (has_deferred_static_rtti) {
                static_cast<deferred_overrider_info&>(*overrider_info)
                    .resolve_type_ids();
            }

            spec_iter->method_index = method.index;
            spec_iter->spec_index = spec_iter - method.overriders.begin();

            ++tr << type_name(overrider_info->type) << " ("
                 << overrider_info->pf << ")\n";
            spec_iter->info = overrider_info;
            spec_iter->vp.reserve(first_info->arity());
            std::size_t param_index = 0;

            for (auto type :
                 range{overrider_info->vp_begin, overrider_info->vp_end}) {
                indent _(tr);
                auto class_ = class_map[rtti::type_index(type)];

                if (!class_) {
                    ++tr << "unknown class error for *virtual* parameter #"
                         << (param_index + 1) << "\n";
                    missing_class error;
                    error.type = type;

                    if constexpr (has_error_handler) {
                        error_handler::error(error);
                    }

                    abort();
                }

                spec_iter->pf = spec_iter->info->pf;
                spec_iter->vp.push_back(class_);
            }

            if (method.covariant_return_type) {
                auto covariant_return_iter = class_map.find(
                    rtti::type_index(overrider_info->return_type));

                if (covariant_return_iter != class_map.end()) {
                    spec_iter->covariant_return_type =
                        covariant_return_iter->second;
                } else {
                    missing_class error;
                    error.type = overrider_info->return_type;

                    if constexpr (has_error_handler) {
                        error_handler::error(error);
                    }

                    abort();
                }
            }

            ++spec_iter;
        }
    }

    for (auto& method : methods) {
        std::size_t param_index = 0;

        for (auto vp : method.vp) {
            for (auto& overrider : method.overriders) {
                if (overrider.vp[param_index] == vp) {
                    continue;
                }

                if (!vp->is_base_of(overrider.vp[param_index])) {
                    missing_base error;
                    error.base = vp->ci[0]->type;
                    error.derived = overrider.vp[param_index]->ci[0]->type;

                    if constexpr (has_error_handler) {
                        error_handler::error(error);
                    }

                    abort();
                }
            }

            vp->used_by_vp.push_back({&method, param_index++});
        }
    }
}

// Slot allocation. The scheme follows the remarks Steven Watanabe made on the
// previous allocator, recorded in issue #19: pull the slots a class may not
// take from the classes deriving from it, instead of pushing reservations up
// to the bases of its derived classes; propagate a single bit after an
// assignment, not whole bit sets; allocate bases before derived classes; and
// place a slot next to, or inside a hole of, the ranges already allocated,
// rather than at the lowest free number. SLOT_ALLOCATION.md gives the full
// account, and the measurements against the previous allocator.
template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::assign_slots() {
    ++tr << "Allocating slots...\n";

    {
        indent _(tr);

        // A root whose cone holds no class with more than one direct base
        // heads a tree, disjoint from every other cone: a class in two cones
        // would have two direct bases somewhere above it. Trees are the common
        // case, and the cheap one: a class's slots follow its parent's, and
        // every v-table is dense from slot 0, in one walk down the tree. The
        // general algorithm below would produce the same layout at a higher
        // cost; the classes of a tree are marked so that it skips them.
        ++class_mark;

        for (auto& cls : classes) {
            if (cls.direct_bases.empty() &&
                std::none_of(
                    cls.transitive_derived.begin(),
                    cls.transitive_derived.end(), [](const class_* derived) {
                        return derived->direct_bases.size() > 1;
                    })) {
                assign_tree_slots(cls, 0);
            }
        }

        // The other classes form lattices. Allocate first the classes whose
        // slot must fit into the most v-tables, while those are still alike:
        // the wider a class's cone, the more it costs to find a slot free in
        // all of it once they have grown apart. A base's cone strictly
        // includes its derived classes' cones, so this also puts bases before
        // derived classes. Between unrelated classes with cones of the same
        // size, the deeper one goes first: it has an inherited range to extend
        // and fewer options. The order of registration decides only what is
        // left.
        std::vector<class_*> order;

        for (auto& cls : classes) {
            if (cls.mark != class_mark) {
                order.push_back(&cls);
            }
        }

        std::stable_sort(
            order.begin(), order.end(), [](const class_* a, const class_* b) {
                if (a->transitive_derived.size() !=
                    b->transitive_derived.size()) {
                    return a->transitive_derived.size() >
                        b->transitive_derived.size();
                }

                return a->transitive_bases.size() > b->transitive_bases.size();
            });

        for (auto cls : order) {
            assign_slots(*cls);
        }
    }

    ++tr << "Allocating v-tables...\n";

    {
        indent _(tr);

        for (auto& cls : classes) {
            if (cls.used_slots.empty()) {
                // Either a class of a tree, whose v-table assign_tree_slots
                // sized, or a class with no slot in it or its ancestors, which
                // has no v-table.
                continue;
            }

            // Leading unused slots are not stored: the v-table starts at the
            // first slot in use, and the class's v-table pointer is offset
            // back by as much.
            cls.first_slot = cls.used_slots.find_first();
            BOOST_ASSERT(cls.first_slot != boost::dynamic_bitset<>::npos);
            cls.vtbl.resize(cls.used_slots.size() - cls.first_slot);
            ++tr << cls << " vtbl: " << cls.first_slot << "-"
                 << (cls.used_slots.size() - 1) << " slots " << cls.used_slots
                 << "\n";
        }
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::assign_tree_slots(
    class_& cls, std::size_t base_slot) {
    using namespace detail;

    cls.mark = class_mark;
    auto next_slot = base_slot;

    for (const auto& mp : cls.used_by_vp) {
        ++tr << "in " << cls << " for "
             << type_name(mp.method->infos[0]->method_type_id) << " parameter "
             << mp.param << ": slot " << next_slot << "\n";
        mp.method->slots[mp.param] = next_slot++;
    }

    // `used_slots` stays empty: the v-table is sized here, and nothing in a
    // lattice ever looks at a class of a tree.
    cls.first_slot = 0;
    cls.vtbl.resize(next_slot);

    for (auto derived : cls.direct_derived) {
        assign_tree_slots(*derived, next_slot);
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::assign_slots(class_& cls) {
    using namespace detail;

    if (cls.used_by_vp.empty()) {
        return;
    }

    // A slot is off limits if any class deriving from `cls` - itself included -
    // already has it in its v-table. That is exactly the set of slots that
    // would collide: two parameters conflict when some class inherits both,
    // and that class is in the cone of each. Nothing else needs tracking, and
    // the order in which classes are allocated cannot affect correctness.
    boost::dynamic_bitset<> unavailable;

    for (auto derived : cls.transitive_derived) {
        merge_into(derived->used_slots, unavailable);
    }

    for (const auto& mp : cls.used_by_vp) {
        auto choice = pick_slot(cls.transitive_derived, unavailable);
        ++tr << "in " << cls << " for "
             << type_name(mp.method->infos[0]->method_type_id) << " parameter "
             << mp.param << ": slot " << choice.slot << ", cost " << choice.cost
             << ", unavailable " << unavailable << "\n";
        mp.method->slots[mp.param] = choice.slot;
        set_bit(unavailable, choice.slot);

        // One bit, to the whole cone: `cls` is in it.
        for (auto derived : cls.transitive_derived) {
            set_bit(derived->used_slots, choice.slot);
        }
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::build_dispatch_tables() {
    using namespace detail;

    for (auto& m : methods) {
        auto first_info = m.infos[0];
        ++tr << "Building dispatch table for "
             << type_name(first_info->method_type_id) << "\n";
        indent _(tr);

        auto dims = m.arity();

        std::vector<group_map> groups;
        groups.resize(dims);

        {
            std::size_t dim = 0;

            for (auto vp : m.vp) {
                auto& dim_group = groups[dim];
                ++tr << "make groups for param #" << dim << ", class " << *vp
                     << "\n";
                indent _(tr);

                for (auto covariant_class : vp->transitive_derived) {
                    ++tr << "overriders applicable to " << *covariant_class
                         << "\n";
                    bitvec mask;
                    mask.resize(m.overriders.size());

                    std::size_t group_index = 0;
                    indent _2(tr);

                    for (auto& spec : m.overriders) {
                        if (spec.vp[dim]->transitive_derived.find(
                                covariant_class) !=
                            spec.vp[dim]->transitive_derived.end()) {
                            ++tr << type_name(spec.info->type) << "\n";
                            mask[group_index] = 1;
                        }
                        ++group_index;
                    }

                    auto& group = dim_group[mask];
                    group.classes.push_back(covariant_class);
                    group.has_concrete_classes = group.has_concrete_classes ||
                        !covariant_class->is_abstract();

                    ++tr << "-> mask: " << mask << "\n";
                }

                ++dim;
            }
        }

        {
            std::size_t stride = 1;
            m.strides.reserve(dims - 1);

            for (std::size_t dim = 1; dim < m.arity(); ++dim) {
                stride *= groups[dim - 1].size();
                ++tr << "    stride for dim " << dim << " = " << stride << "\n";
                m.strides.push_back(stride);
            }
        }

        for (std::size_t dim = 0; dim < m.arity(); ++dim) {
            indent _(tr);
            std::size_t group_num = 0;

            for (auto& [mask, group] : groups[dim]) {
                ++tr << "groups for dim " << dim << ":\n";
                indent _(tr);
                ++tr << group_num << " mask " << mask << ":\n";

                for (auto cls : group.classes) {
                    indent _(tr);
                    ++tr << type_name(cls->ci[0]->type) << "\n";
                    auto& entry = cls->vtbl[m.slots[dim] - cls->first_slot];
                    entry.method_index = m.index;
                    entry.vp_index = dim;
                    entry.group_index = group_num;
                }

                ++group_num;
            }
        }

        {
            ++tr << "building dispatch table\n";
            bitvec all(m.overriders.size());
            all = ~all;
            build_dispatch_table(m, dims - 1, groups.end() - 1, all, true);

            if (m.arity() > 1) {
                indent _(tr);
                m.report.cells = 1;
                ++tr << "dispatch table rank: ";
                const char* prefix = "";

                for (const auto& dim_groups : groups) {
                    m.report.cells *= dim_groups.size();
                    tr << prefix << dim_groups.size();
                    prefix = " x ";
                }

                prefix = ", concrete only: ";

                for (const auto& dim_groups : groups) {
                    auto cells = std::count_if(
                        dim_groups.begin(), dim_groups.end(),
                        [](const auto& group) {
                            return group.second.has_concrete_classes;
                        });
                    tr << prefix << cells;
                    prefix = " x ";
                }

                tr << "\n";
            }

            print(m.report);
            accumulate(m.report, report);
        }
    }
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::build_dispatch_table(
    method& m, std::size_t dim,
    std::vector<group_map>::const_iterator group_iter, const bitvec& candidates,
    bool concrete) {
    using namespace detail;

    indent _(tr);
    std::size_t group_index = 0;

    for (const auto& [group_mask, group] : *group_iter) {
        auto mask = candidates & group_mask;

        if constexpr (has_trace) {
            ++tr << "group " << dim << "/" << group_index << " mask " << mask
                 << "\n";
            indent _(tr);
            for (auto cls : range{group.classes.begin(), group.classes.end()}) {
                ++tr << type_name(cls->ci[0]->type) << "\n";
            }
        }

        if (dim == 0) {
            std::vector<overrider*> overriders;
            std::size_t i = 0;

            for (auto& spec : m.overriders) {
                if (mask[i]) {
                    overriders.push_back(&spec);
                }
                ++i;
            }

            if constexpr (has_trace) {
                ++tr << "select best of:\n";
                indent _(tr);

                for (auto& app : overriders) {
                    ++tr << "#" << app->spec_index << " "
                         << type_name(app->info->type) << "\n";
                }
            }

            std::vector<overrider*> dominants = overriders;
            std::size_t pick, remaining;

            select_dominant_overriders(dominants, pick, remaining);

            if (remaining == 0) {
                indent _(tr);
                ++tr << "not implemented\n";
                m.dispatch_table.push_back(&m.not_implemented);
                ++m.report.not_implemented;
            } else {
                if constexpr (!has_option<n2216>) {
                    if (remaining > 1) {
                        ++tr << "ambiguous\n";
                        m.dispatch_table.push_back(&m.ambiguous);
                        ++m.report.ambiguous;
                        continue;
                    }
                }

                auto overrider = dominants[pick];
                m.dispatch_table.push_back(overrider);
                ++tr;

                tr << "-> #" << overrider->spec_index << " "
                   << type_name(overrider->info->type)
                   << " pf = " << overrider->info->pf;

                if (remaining > 1) {
                    tr << " (ambiguous)";
                    ++m.report.ambiguous;
                }

                tr << "\n";

                // -------------------------------------------------------------
                // next

                // First remove the dominant overriders from the overriders.
                // Note that the dominants appear in the overriders in the same
                // relative order.
                auto candidate = overriders.begin();
                remaining = 0;

                for (auto dominant : dominants) {
                    if (*candidate == dominant) {
                        *candidate = nullptr;
                    } else {
                        ++remaining;
                    }

                    ++candidate;
                }

                if (remaining == 0) {
                    ++tr << "no 'next'\n";
                    overrider->next = &m.not_implemented;
                } else {
                    if constexpr (has_trace) {
                        ++tr << "for 'next', select best of:\n";
                        indent _(tr);

                        for (auto& app : overriders) {
                            if (app) {
                                ++tr << "#" << app->spec_index << " "
                                     << type_name(app->info->type) << "\n";
                            }
                        }
                    }

                    select_dominant_overriders(overriders, pick, remaining);

                    if constexpr (!has_option<n2216>) {
                        if (remaining > 1) {
                            ++tr << "ambiguous 'next'\n";
                            overrider->next = &m.ambiguous;
                            continue;
                        }
                    }

                    auto next_overrider = overriders[pick];
                    overrider->next = next_overrider;

                    ++tr << "-> #" << next_overrider->spec_index << " "
                         << type_name(next_overrider->info->type)
                         << " pf = " << next_overrider->info->pf;

                    if (remaining > 1) {
                        tr << " (ambiguous)";
                        // do not increment m.report.ambiguous, for same reason
                    }

                    tr << "\n";
                }
            }
        } else {
            build_dispatch_table(
                m, dim - 1, group_iter - 1, mask,
                concrete && group.has_concrete_classes);
        }

        ++group_index;
    }
}

inline void detail::generic_compiler::accumulate(
    const method_report& partial, report& total) {
    total.cells += partial.cells;
    total.not_implemented += partial.not_implemented != 0;
    total.ambiguous += partial.ambiguous != 0;
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::write_global_data() {
    using namespace policies;
    using namespace detail;

    // Three steps: stage, initialize the policies, commit. Everything that
    // can fail happens in the first two, and neither writes anything shared
    // except the policies' own states, which the transaction restores on
    // failure: the dispatch data is built in a local vector, and each class'
    // v-table pointer is staged in its class_, where the policies read it.
    // Only then are the shared locations patched - the method_infos' slots
    // and strides, the overriders' `next`, the class_infos' static_vptr - and
    // the dispatch data swapped in; none of that can throw. If a policy
    // throws, the registry still holds the previous dispatch state, complete
    // and consistent, rather than pointers into a vector that unwinding has
    // just freed.

    auto dispatch_data_size = std::accumulate(
        methods.begin(), methods.end(), std::size_t(0),
        [](std::size_t sum, const method& m) {
            // msvc doesn't like (auto sum, auto& m) (C2187), go figure...
            return sum + m.dispatch_table.size();
        });
    dispatch_data_size = std::accumulate(
        classes.begin(), classes.end(), dispatch_data_size,
        [](auto sum, const auto& cls) { return sum + cls.vtbl.size(); });

    std::vector<detail::word> new_dispatch_data(dispatch_data_size);
    auto gv_first = new_dispatch_data.data();
    [[maybe_unused]] auto gv_last = gv_first + dispatch_data_size;
    auto gv_iter = gv_first;

    ++tr << "Initializing multi-method dispatch tables at " << gv_iter << "\n";

    for (auto& m : methods) {
        // Uni-methods just need an index in the method table, written at
        // commit time along with the multi-methods' slots and strides.
        if (m.infos[0]->arity() > 1) {
            if constexpr (has_trace) {
                ++tr << rflush(4, dispatch_data_size) << " " << " method #"
                     << m.dispatch_table[0]->method_index << " "
                     << type_name(m.infos[0]->method_type_id) << "\n";
                indent _(tr);

                for (auto& entry : m.dispatch_table) {
                    ++tr << "spec #" << entry->spec_index << " "
                         << spec_name(m, entry) << "\n";
                }
            }

            m.gv_dispatch_table = gv_iter;
            BOOST_ASSERT(gv_iter + m.dispatch_table.size() <= gv_last);
            gv_iter = std::transform(
                m.dispatch_table.begin(), m.dispatch_table.end(), gv_iter,
                [](auto spec) { return spec->pf; });
        }
    }

    ++tr << "'next' pointers\n";

    for (auto& m : methods) {
        auto first_info = m.infos[0];
        indent _(tr);
        ++tr << "method #" << " " << type_name(first_info->method_type_id)
             << "\n";

        for (auto& overrider : m.overriders) {
            if (overrider.next) {
                ++tr << "#" << overrider.spec_index << " "
                     << spec_name(m, &overrider) << " -> ";

                tr << "#" << overrider.next->spec_index << " "
                   << spec_name(m, overrider.next);
            } else {
                tr << "none";
            }

            tr << "\n";
        }
    }

    ++tr << "Initializing v-tables at " << gv_iter << "\n";

    for (auto& cls : classes) {
        cls.vptr = gv_iter - cls.first_slot;

        ++tr << rflush(4, gv_iter - gv_first) << " " << gv_iter << " vtbl for "
             << cls << " slots " << cls.first_slot << "-"
             << (cls.first_slot + cls.vtbl.size() - 1) << "\n";
        indent _(tr);

        for (auto& entry : cls.vtbl) {
            ++tr << "method #" << entry.method_index << " ";
            auto& method = methods[entry.method_index];

            if (method.arity() == 1) {
                auto spec = method.dispatch_table[entry.group_index];
                tr << "spec #" << spec->spec_index << "\n";
                indent _(tr);
                ++tr << type_name(method.infos[0]->method_type_id) << "\n";
                ++tr << spec_name(method, spec);
                BOOST_ASSERT(gv_iter + 1 <= gv_last);
                *gv_iter++ = spec->pf;
            } else {
                tr << "vp #" << entry.vp_index << " group #"
                   << entry.group_index << "\n";
                indent _2(tr);
                ++tr << type_name(method.infos[0]->method_type_id);
                BOOST_ASSERT(gv_iter + 1 <= gv_last);

                if (entry.vp_index == 0) {
                    *gv_iter++ = std::uintptr_t(
                        method.gv_dispatch_table + entry.group_index);
                } else {
                    *gv_iter++ = entry.group_index;
                }
            }

            tr << "\n";
        }
    }

    ++tr << rflush(4, dispatch_data_size) << " " << gv_iter << " end\n";

    detail::registry_state_transaction<registry> transaction;
    detail::initialize_policies<registry>::fn(*this, options);
    transaction.commit();

    // Commit. Nothing from here on can throw.

    ++tr << "Installing\n";

    for (auto& m : methods) {
        auto first_info = m.infos[0];

        if (first_info->arity() == 1) {
            first_info->slots_strides_ptr[0] = m.slots[0];
        } else {
            auto strides_iter = std::copy(
                m.slots.begin(), m.slots.end(), first_info->slots_strides_ptr);
            std::copy(m.strides.begin(), m.strides.end(), strides_iter);
        }

        // Propagate slots_strides values from the local method_info to all
        // other module copies of the same method. Each module's `fn` has its
        // own slots_strides[] array; dispatch reads it directly, so every
        // copy must hold the same values.
        auto count = 2 * first_info->arity() - 1;

        for (auto copy : m.infos) {
            if (copy != first_info) {
                std::copy(
                    first_info->slots_strides_ptr,
                    first_info->slots_strides_ptr + count,
                    copy->slots_strides_ptr);
            }
        }

        for (auto& overrider : m.overriders) {
            if (overrider.next) {
                *overrider.info->next =
                    reinterpret_cast<void (*)()>(overrider.next->pf);
            }
        }
    }

    for (auto& cls : classes) {
        for (auto& ci : cls.ci) {
            *ci->static_vptr = cls.vptr;
        }
    }

    new_dispatch_data.swap(static_::st.dispatch_data);
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::select_dominant_overriders(
    std::vector<overrider*>& candidates, std::size_t& pick,
    std::size_t& remaining) {

    pick = 0;
    remaining = 0;

    for (size_t i = 0; i < candidates.size(); ++i) {
        if (candidates[i]) {
            for (size_t j = i + 1; j < candidates.size(); ++j) {
                if (candidates[j]) {
                    if (is_more_specific(candidates[i], candidates[j])) {
                        candidates[j] = nullptr;
                    } else if (is_more_specific(candidates[j], candidates[i])) {
                        candidates[i] = nullptr;
                        break; // this one is dead
                    }
                }
            }
        }

        if (candidates[i]) {
            pick = i;
            ++remaining;
        }
    }

    if (remaining <= 1) {
        return;
    }

    if constexpr (has_option<n2216>) {
        if (!candidates[pick]->covariant_return_type) {
            return;
        }

        remaining = 0;

        for (size_t i = 0; i < candidates.size(); ++i) {
            if (candidates[i]) {
                for (size_t j = i + 1; j < candidates.size(); ++j) {
                    if (candidates[j]) {
                        BOOST_ASSERT(candidates[i] != candidates[j]);

                        if (candidates[i]->covariant_return_type->is_base_of(
                                candidates[j]->covariant_return_type)) {
                            candidates[i] = nullptr;
                        } else if (
                            candidates[j]->covariant_return_type->is_base_of(
                                candidates[i]->covariant_return_type)) {
                            candidates[j] = nullptr;
                        }
                    }
                }
            }

            if (candidates[i]) {
                pick = i;
                ++remaining;
            }
        }
    }
}

template<class... Policies>
template<class... Options>
auto registry<Policies...>::compiler<Options...>::is_more_specific(
    const overrider* a, const overrider* b) -> bool {
    bool result = false;

    auto a_iter = a->vp.begin(), a_last = a->vp.end(), b_iter = b->vp.begin();

    for (; a_iter != a_last; ++a_iter, ++b_iter) {
        if (*a_iter != *b_iter) {
            if ((*b_iter)->transitive_derived.find(*a_iter) !=
                (*b_iter)->transitive_derived.end()) {
                result = true;
            } else if (
                (*a_iter)->transitive_derived.find(*b_iter) !=
                (*a_iter)->transitive_derived.end()) {
                return false;
            }
        }
    }

    return result;
}

template<class... Policies>
template<class... Options>
auto registry<Policies...>::compiler<Options...>::is_base(
    const overrider* a, const overrider* b) -> bool {
    bool result = false;

    auto a_iter = a->vp.begin(), a_last = a->vp.end(), b_iter = b->vp.begin();

    for (; a_iter != a_last; ++a_iter, ++b_iter) {
        if (*a_iter != *b_iter) {
            if ((*a_iter)->transitive_derived.find(*b_iter) ==
                (*a_iter)->transitive_derived.end()) {
                return false;
            } else {
                result = true;
            }
        }
    }

    return result;
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::print(
    const method_report& r) const {
    ++tr;

    if (r.cells) {
        // only for multi-methods, uni-methods don't have dispatch tables
        ++tr << r.cells << " dispatch table cells, ";
    }

    tr << r.not_implemented << " not implemented, " << r.ambiguous
       << " ambiguous\n";
}

template<class... Policies>
template<class... Options>
void registry<Policies...>::compiler<Options...>::print_slots() {
    if constexpr (has_trace) {
        if (!tr.on) {
            return;
        }

        using namespace detail;

        // Slot numbering is scoped to a connected component of the class
        // graph, so partition the classes into components first. A component
        // is identified by the classes in it that have no direct bases; there
        // is more than one only in presence of multiple inheritance.
        std::unordered_map<const class_*, std::size_t> component;
        std::size_t component_count = 0;

        for (auto& seed : classes) {
            if (component.find(&seed) != component.end()) {
                continue;
            }

            auto id = component_count++;
            component[&seed] = id;
            std::vector<class_*> todo{&seed};

            while (!todo.empty()) {
                auto cls = todo.back();
                todo.pop_back();

                for (auto neighbors :
                     {&cls->direct_bases, &cls->direct_derived}) {
                    for (auto next : *neighbors) {
                        if (component.emplace(next, id).second) {
                            todo.push_back(next);
                        }
                    }
                }
            }
        }

        // Collect the members in 'classes' order, for a deterministic trace.
        std::vector<std::vector<class_*>> lattices(component_count);

        for (auto& cls : classes) {
            lattices[component[&cls]].push_back(&cls);
        }

        ++tr << "Used slots:\n";
        indent _(tr);

        for (auto& lattice : lattices) {
            std::vector<class_*> roots;

            for (auto cls : lattice) {
                if (cls->direct_bases.empty()) {
                    roots.push_back(cls);
                }
            }

            ++tr << roots << "\n";
            indent _2(tr);

            struct entry {
                std::size_t slot;
                class_* cls;
                parameter mp;
            };

            std::vector<entry> slots;

            for (auto cls : lattice) {
                for (const auto& mp : cls->used_by_vp) {
                    slots.push_back({mp.method->slots[mp.param], cls, mp});
                }
            }

            std::stable_sort(
                slots.begin(), slots.end(),
                [](const entry& a, const entry& b) { return a.slot < b.slot; });

            ++tr << "slots:\n";

            {
                indent _3(tr);

                for (const auto& e : slots) {
                    ++tr << e.slot << ": in " << *e.cls << " for "
                         << type_name(e.mp.method->infos[0]->method_type_id)
                         << " parameter " << e.mp.param << "\n";
                }
            }

            ++tr << "v-tables:\n";

            {
                indent _3(tr);

                for (auto cls : lattice) {
                    if (cls->vtbl.empty()) {
                        continue;
                    }

                    ++tr << *cls << " slots " << cls->first_slot << "-"
                         << (cls->first_slot + cls->vtbl.size() - 1) << "\n";
                }
            }
        }
    }
}

//! Initialize a registry.
//!
//! Initialize the @ref registry passed as an explicit function template
//! argument, or @ref default_registry if the registry is not specified. The
//! default can be changed by defining @ref BOOST_OPENMETHOD_DEFAULT_REGISTRY.
//! Option objects can be passed to change the behavior of the function.
//! Currently two options exist:
//! @li @ref trace Enable tracing of the initialization process.
//! @li @ref n2216 Enable resolution of ambiguities according to the N2216
//! paper.
//!
//! `initialize` must be called, typically at the beginning of `main`, before
//! using any of the methods in a registry. It sets up the v-tables,
//! multi-method dispatch tables, and any other data required by the policies.
//!
//! The function returns an object of an unspecified type that contains a
//! `report` member, itself an object of an unspecified type, thatcontains the
//! following members:
//! @li @c std::size_t @c cells: The number of cells in all multi-method dispatch
//! tables.
//! @li @c std::size_t @c not_implemented: The number of multi-method dispatch tables that
//! contain at least one not implemented entry.
//! @li @c std::size_t @c ambiguous: The number of multi-method dispatch tables that contain at
//! least one ambiguous entry.
//!
//! @note
//! A translation unit that calls `initialize` must include the
//! `<boost/openmethod/initialize.hpp>` header.
//!
//! @note
//! Each policy's `initialize` is called in the order the policies appear in the
//! registry's `policy_list` (left to right). If a policy depends on another
//! policy having been initialized first, the dependency must appear *earlier*
//! in the list; ensuring this is the user's responsibility. @ref finalize
//! finalizes the policies in the reverse order.
//!
//! @tparam Registry The registry to initialize.
//! @tparam Options... Zero or more option types, deduced from the function
//! arguments.
//! @param options Zero or more option objects.
//! @return An object of an unspecified type.
//!
//! @par Errors
//!
//! @li @ref missing_class: A class used in a virtual parameter was not
//! registered.
//! @li The registry's policies may report additional errors.
//!
//! @par Exception safety
//!
//! If `initialize` throws - because a policy's `initialize` does, or an
//! allocation fails - the registry keeps the dispatch state it had before the
//! call: no static v-table pointer, `next` pointer, dispatch table or policy
//! state is modified. The registry is nonetheless marked as not initialized,
//! since that state does not reflect the current registrations; `initialize`
//! must be called again, successfully, before any method is called. Policy
//! states are restored from a copy, so a policy's `state` must be copyable.
//!
//! @par Example
//!
//! Initialize the default registry with tracing enabled, and exit with an error
//! message if there were any possibility of a @reg bad_call error. User may run
//! the program again after setting environment variable
//! `BOOST_OPENMETHOD_TRACE` to `1` to troubleshoot.
//!
//! include:initialize.cpp#report
//!
//! @see [Methods and Overriders](xref:ROOT:basics.adoc)
//! @see [Shared Libraries](xref:ROOT:shared_libraries.adoc)
template<class Registry = BOOST_OPENMETHOD_DEFAULT_REGISTRY, class... Options>
inline auto initialize(Options&&... options) {
    if (detail::odr_check<Registry>::count > 1) {
        // Multiple definitions of default_registry detected.
        // This indicates an ODR violation.
        // Signal a final_error using the error handler, then abort.
        if constexpr (Registry::has_error_handler) {
            Registry::error_handler::error(odr_violation());
        }

        std::abort();
    }

    typename Registry::template compiler<Options...> comp(
        std::forward<Options>(options)...);
    comp.initialize();

    return comp;
}

namespace detail {

// See the BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN_MSVC_SAFE definition near
// has_initialize, above, for why this needs the MSVC-safe form too.
BOOST_OPENMETHOD_DETAIL_HAS_STATIC_FN_MSVC_SAFE(finalize);

// Call finalize on a single policy if it has the function. Mirror of
// initialize_policy.
template<typename Policy, typename Registry, typename Options>
void finalize_policy(const Options& options) {
    using PolicyFn = typename Policy::template fn<Registry>;
    if constexpr (has_finalize<PolicyFn, const Options&>) {
        PolicyFn::finalize(options);
    }
}

// Policies are finalized in the reverse of `policy_list` order — the mirror of
// initialize_policies — so a policy is torn down before the ones it depends on.
template<
    typename Registry,
    typename Policies = mp11::mp_reverse<typename Registry::policy_list>>
struct finalize_policies;

template<typename Registry, typename... Policies>
struct finalize_policies<Registry, mp11::mp_list<Policies...>> {
    template<typename Options>
    static void fn(const Options& options) {
        (finalize_policy<Policies, Registry>(options), ...);
    }
};

} // namespace detail

template<class... Policies>
template<class... Options>
auto registry<Policies...>::finalize(Options... opts) -> void {
    std::tuple<Options...> options(opts...);
    detail::finalize_policies<registry>::fn(options);
    static_::st.dispatch_data.clear();
    static_::st.initialized = false;
}

//! Release resources held by registry.
//!
//! `finalize` may be called to release any resources allocated by
//! @ref registry::initialize.
//!
//! @note
//! A translation unit that contains a call to `finalize` must include the
//! `<boost/openmethod/initialize.hpp>` header.
//!
//! @note
//! Each policy's `finalize` is called in the reverse of the registry's
//! `policy_list` order, the mirror of @ref initialize, so a policy is finalized
//! before the policies it depends on.
//!
//! @tparam Registry The registry to finalize.
//! @tparam Options... Zero or more option types, deduced from the function
//! arguments.
//! @param options Zero or more option objects.
//!
//! @see [Shared Libraries](xref:ROOT:shared_libraries.adoc)
template<class Registry = BOOST_OPENMETHOD_DEFAULT_REGISTRY, class... Options>
inline auto finalize(Options&&... opts) -> void {
    Registry::finalize(std::forward<Options>(opts)...);
}

} // namespace boost::openmethod

#ifdef _MSC_VER
#pragma warning(pop)
#endif

#endif
