hana-gperf.cpp

// @author Vinícius dos Santos Oliveira
// I'm releasing this snippet as public domain.
// Do as you like.

#include <boost/hana/functional/overload_linearly.hpp>
#include <boost/hana/functional/overload.hpp>
#include <boost/hana/functional/always.hpp>
#include <boost/hana/fold_right.hpp>
#include <boost/hana/drop_back.hpp>
#include <boost/hana/not_equal.hpp>
#include <boost/hana/greater.hpp>
#include <boost/hana/minimum.hpp>
#include <boost/hana/reverse.hpp>
#include <boost/hana/string.hpp>
#include <boost/hana/minus.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/fold.hpp>
#include <boost/hana/mult.hpp>
#include <boost/hana/size.hpp>
#include <boost/hana/sort.hpp>
#include <boost/hana/set.hpp>
#include <boost/hana/zip.hpp>

#include <string_view>
#include <iostream>

struct lua_State;

namespace hana = boost::hana;

namespace dispatch_table {
namespace detail {
using hana::literals::operator""_c;

// string_view compares string size before string contents. Therefore, string
// size here already performs work similar to the hash table usage. On the event
// where all string sizes differ, we don't generate another hash function.
struct ConstantHash
{
    static constexpr auto value = hana::always(hana::size_c<0>);
    static constexpr auto first_pass = hana::always(hana::true_c);
};

template<class Strings>
struct Hash
{
    static constexpr std::size_t smallest_pattern_size = hana::minimum(
        hana::transform(Strings{}, hana::size));

    // We're after a cheap hash for our static search structure, not a perfect
    // hash.
    static constexpr auto value = []() {
        // The algorithm to find the suitable indexes is roughly divided into
        // these steps:
        //
        // * Produce indexes [0, N).
        // * Produce reverse indexes [N, 1].
        // * Whether and index is reversed is indicated by the boolean constant
        //   that follows the index. `true` means reversed. Reverse index count
        //   from the end iterator.
        // * We use N=smallest_pattern_size because we don't want to perform
        //   bounds checking later.
        // * Concat the two sequences.
        auto initial_idxs = hana::concat(
            hana::transform(
                hana::to_tuple(
                    hana::range_c<std::size_t, 0, smallest_pattern_size>),
                [](auto&& i) { return hana::make_tuple(i, hana::false_c); }
            ),
            hana::reverse(hana::transform(
                hana::to_tuple(
                    hana::range_c<std::size_t, 1, smallest_pattern_size + 1>),
                [](auto&& i) { return hana::make_tuple(i, hana::true_c); }
            ))
        );
        // * Apply all strings to each index. The application will compute the
        //   hash value, store it into a set and append the set's length to the
        //   end of the index tuple. This length indicates a score.
        // * Remove all indexes whose score is 1. They can't be used to
        //   differentiate between any two strings.
        auto idxs_plus_score = initial_idxs |
            [](auto&& e) {
                auto score = hana::size(hana::to_set(hana::transform(
                    Strings{},
                    [idx=e[0_c],rev=e[1_c]](auto&& str) {
                        return hana::if_(
                            rev, str[hana::size(str) - idx], str[idx]);
                    }
                )));
                return hana::if_(
                    score == hana::size_c<1>,
                    hana::make_tuple(),
                    hana::make_tuple(hana::insert(e, hana::int_c<2>, score)));
            };
        // * Apply a stable sort by decreasing score.
        // * Limit the indexes list to length 4 (i.e. bytes in an int32_t).
        // * Discard score.
        auto uncompressed_hash = hana::transform(
            hana::take_front_c<4>(hana::sort(
                idxs_plus_score,
                [](auto&& l, auto&& r) { return hana::greater(l[2_c], r[2_c]); }
            )),
            hana::take_front_c<2>
        );
        // * Consider the result as a single hash. Generate more hashes by
        //   discarding tail until new permutations are no longer possible.
        auto final_round_choices = hana::while_(
            [](auto&& e) { return hana::size(e[0_c]) != hana::size_c<1>; },
            hana::make_tuple(uncompressed_hash),
            [](auto&& e) {
                return hana::insert(e, 0_c, hana::drop_back(e[0_c]));
            }
        );
        // * Compute a score again by applying all the strings to each hash
        //   candidate. But first we create the function that generate the hash
        //   function out of the hash spec.
        // * Sort by score plus hash complexity (i.e. all else being equal,
        //   cheaper hashes stay at the front) and get the best one.
        auto hash_gen = [](auto&& spec) {
            return hana::fold(
                hana::zip(
                    spec,
                    hana::transform(
                        hana::to_tuple(
                            hana::make_range(hana::size_c<0>, hana::size(spec))
                        ),
                        hana::_ * hana::integral_c<std::uint32_t, 8>)),
                hana::always(hana::integral_c<std::uint32_t, 0>),
                [](auto&& acc, auto&& subhash) {
                    return [acc,subhash](const auto& string) {
                        auto size = hana::overload(
                            [](std::string_view str) { return str.size(); },
                            hana::size
                        );
                        auto at = hana::overload_linearly(
                            [](std::string_view str, std::size_t i) {
                                return std::uint32_t(str[i]);
                            },
                            [](auto&& xs, auto&& i) {
                                return hana::to<
                                    hana::integral_constant_tag<std::uint32_t>
                                >(hana::at(xs, i));
                            }
                        );
                        auto idx = hana::if_(
                            /*reverse_index=*/subhash[0_c][1_c],
                            size(string) - subhash[0_c][0_c],
                            subhash[0_c][0_c]);
                        return acc(string) + (at(string, idx) << subhash[1_c]);
                    };
                }
            );
        };
        return hash_gen(/*spec=*/hana::first(hana::front(hana::sort(
            hana::transform(
                final_round_choices,
                [hash_gen](auto&& e) {
                    auto score = hana::size(hana::to_set(
                        hana::transform(Strings{}, hash_gen(e))));
                    return hana::make_pair(e, score);
                }),
            [](auto&& l, auto&& r) {
                return hana::greater(hana::second(l), hana::second(r));
            }
        ))));
    }();

    static constexpr bool first_pass(std::string_view str)
    {
        // So later code won't have to perform bounds checking when computing
        // hash
        if (str.size() < smallest_pattern_size)
            return false;

        return true;
    }
};

template<class Xs>
constexpr bool all_sizes_differ(const Xs& xs)
{
    return hana::size(hana::to_set(
        hana::transform(hana::transform(xs, hana::first), hana::size)
    )) == hana::size(xs);
}
} // namespace detail

// Even if a perfect-hash is generated, a walk through the whole table is
// done. The rationale is to keep the generated code small. Also, for our
// use-case, not-found is an exceptional case, so we purposefully don't optimize
// for it.
template<class Xs, class Fallback, class... Args>
auto dispatch(Xs xs, Fallback fallback, std::string_view key, Args&&... args)
    -> decltype(fallback(key, std::forward<Args>(args)...))
{
    std::conditional_t<
        detail::all_sizes_differ(xs),
        detail::ConstantHash,
        detail::Hash<decltype(hana::transform(xs, hana::first))>
    > hash;
    if (!hash.first_pass(key))
        return fallback(key, std::forward<Args>(args)...);

    return hana::fold_right(
        xs,
        fallback,
        [hash](const auto& arm, const auto& acc) {
            return [hash,arm,acc](std::string_view key, auto&&... args) {
                auto pattern_ct = hana::first(arm);
                std::string_view pattern{
                    pattern_ct.c_str(), hana::size(pattern_ct)};
                if (hash.value(pattern_ct) == hash.value(key) &&
                    pattern == key) {
                    return hana::second(arm)(
                        std::forward<decltype(args)>(args)...);
                } else {
                    return acc(key, std::forward<decltype(args)>(args)...);
                }
            };
        }
    )(key, std::forward<Args>(args)...);
}
} // namespace dispatch_table

int foobar(std::string_view key, lua_State* L)
{
    return dispatch_table::dispatch(
        hana::make_tuple(
            hana::make_pair(
                BOOST_HANA_STRING("joinable"),
                [](lua_State*) -> int { return 1; }
            ),
            hana::make_pair(
                BOOST_HANA_STRING("join"),
                [](lua_State*) -> int { return 2; }
            ),
            hana::make_pair(
                BOOST_HANA_STRING("detach"),
                [](lua_State*) -> int { return 3; }
            ),
            hana::make_pair(
                BOOST_HANA_STRING("interrupt"),
                [](lua_State*) -> int { return 4; }
            ),
            hana::make_pair(
                BOOST_HANA_STRING("interruption_caught"),
                [](lua_State*) -> int { return 5; }
            )
        ),
        [](std::string_view /*key*/, lua_State*) -> int { return -1; },
        key,
        L
    );
}

int main()
{
    std::string input;
    std::getline(std::cin, input);
    std::cout << foobar(input, nullptr) << std::endl;
}