libdpf/include/dpf/eval_full.hpp

/// @file dpf/eval_full.hpp
/// @brief Evaluate every input in the DPF domain.
/// @details Equivalent to `eval_interval` from
///          `std::numeric_limits<input_type>::min()` through `max()`.
///          When the input offset is not yet assigned, use `defer_eval_full`
///          (full-domain identity eval plus a deferred rotation view).
///          @snippet evaluation/eval_full.cpp eval-full
/// @author Ryan Henry <ryan.henry@ucalgary.ca>
/// @author Christopher Jiang <christopher.jiang@ucalgary.ca>
/// @copyright Copyright (c) 2019-2024 Ryan Henry and [others](@ref authors)
/// @license Released under a GNU General Public v2.0 (GPLv2) license;
///          see [LICENSE.md](@ref license) for details.

#ifndef LIBDPF_INCLUDE_DPF_EVAL_FULL_HPP__
#define LIBDPF_INCLUDE_DPF_EVAL_FULL_HPP__

#include <portable-snippets/builtin/builtin.h>
#include "hedley/hedley.h"

#include <cstddef>
#include <type_traits>
#include <utility>
#include <limits>

#include "dpf/dpf_key.hpp"
#include "dpf/eval_common.hpp"
#include "dpf/eval_target.hpp"
#include "dpf/output_buffer.hpp"
#include "dpf/interval_memoizer.hpp"
#include "dpf/rotation_iterable.hpp"
#include "dpf/subinterval_iterable.hpp"
#include "dpf/verifiable.hpp"

namespace dpf
{

namespace internal
{

template <std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          typename IntervalMemoizer,
          std::size_t ...IIs,
          std::enable_if_t<dpf::is_wildcard_v<typename DpfKey::raw_input_type>, bool> = false>
auto eval_full(const DpfKey & dpf, OutputBuffers && outbufs,
    IntervalMemoizer && memoizer, std::index_sequence<IIs...>,
    proof_token * pi = nullptr)
{
    using dpf_type = DpfKey;
    using input_type = typename dpf_type::input_type;
    auto offset = dpf.offset_x(0);  // N.B.: throws if dpf is not ready

    dpf::internal::eval_interval_impl<Is...>(dpf,
            std::numeric_limits<input_type>::min(),
            std::numeric_limits<input_type>::max(),
            outbufs, memoizer, std::make_index_sequence<sizeof...(Is)>(), pi);

    return utils::make_tuple(dpf::rotation_iterable(std::begin(utils::get<IIs>(outbufs)), std::end(utils::get<IIs>(outbufs)), offset)...);
}

template <std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          typename IntervalMemoizer,
          std::size_t ...IIs,
          std::enable_if_t<!dpf::is_wildcard_v<typename DpfKey::raw_input_type>, bool> = false>
auto eval_full(const DpfKey & dpf, OutputBuffers && outbufs,
    IntervalMemoizer && memoizer, std::index_sequence<IIs...>,
    proof_token * pi = nullptr)
{
    using dpf_type = DpfKey;
    using input_type = typename dpf_type::input_type;

    dpf::internal::eval_interval_impl<Is...>(dpf,
            std::numeric_limits<input_type>::min(),
            std::numeric_limits<input_type>::max(),
            outbufs, memoizer, std::make_index_sequence<sizeof...(Is)>(), pi);

    return utils::make_tuple(
        subinterval_iterable(std::begin(utils::get<IIs>(outbufs)),
            utils::size(utils::get<IIs>(outbufs)),
            std::size_t{0},
            utils::get<IIs>(outbufs).size() - 1,
            std::size_t{0},
            std::size_t{0})...);
}

}  // namespace internal

/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          typename IntervalMemoizer,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf, OutputBuffers && outbufs,
    IntervalMemoizer && memoizer, proof_token * pi = nullptr)
{
    assert_not_wildcard_output<I, Is...>(dpf);

    return internal::eval_full<I, Is...>(dpf, outbufs, memoizer,
        std::make_index_sequence<1+sizeof...(Is)>(), pi);
}

/// @brief Evaluate the whole domain and fold a once-per-BFS-node VDPF proof.
/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          typename IntervalMemoizer,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf, OutputBuffers && outbufs,
    IntervalMemoizer && memoizer, prove_ref pr)
{
    static_assert(DpfKey::is_verifiable,
        "eval_full(..., prove(π)): key must carry dpf::verifiable");
    detail::vdpf::init_proof(pr.token, dpf);
    auto out = eval_full<I, Is...>(dpf, std::forward<OutputBuffers>(outbufs),
        std::forward<IntervalMemoizer>(memoizer), &pr.token);
    detail::vdpf::fold_output_binding(pr.token, dpf);
    return out;
}

/// @brief Evaluate the whole domain and fold each written output into a sketch.
/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          typename IntervalMemoizer,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf, OutputBuffers && outbufs,
    IntervalMemoizer && memoizer, sketch_ref & sk)
{
    static_assert(DpfKey::is_extractable,
        "eval_full(..., sketch(σ)): key must carry dpf::extractable");
    auto ret = eval_full<I, Is...>(dpf, outbufs,
        std::forward<IntervalMemoizer>(memoizer));
    if constexpr (sizeof...(Is) == 0)
    {
        for (std::size_t k = 0; k < utils::size(outbufs); ++k)
            sk.absorb(outbufs[k]);
    }
    return ret;
}

/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true,
          std::enable_if_t<!std::is_base_of_v<
              dpf::interval_memoizer_base<unwrap_party_key_t<DpfKey>>,
              std::decay_t<OutputBuffers>>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf, OutputBuffers & outbufs)  // NOLINT(runtime/references)
{
    // The full-domain workspace is keyed only by the key type. Reusing it
    // drops a heap allocation per call and lets a repeated key skip the
    // interior rebuild (assign_interval keeps the last level).
    thread_local auto memo = dpf::make_basic_full_memoizer<DpfKey>();
    return eval_full<I, Is...>(dpf, outbufs, memo);
}

/// @brief Evaluate the whole domain into `outbufs` and fold a VDPF proof.
/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true,
          std::enable_if_t<!std::is_base_of_v<
              dpf::interval_memoizer_base<unwrap_party_key_t<DpfKey>>,
              std::decay_t<OutputBuffers>>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf, OutputBuffers & outbufs, prove_ref pr)  // NOLINT(runtime/references)
{
    static_assert(DpfKey::is_verifiable,
        "eval_full(..., prove(π)): key must carry dpf::verifiable");
    return eval_full<I, Is...>(dpf, outbufs,
        dpf::make_basic_full_memoizer(dpf), pr);
}

/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename IntervalMemoizer,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true,
          std::enable_if_t<std::is_base_of_v<
              dpf::interval_memoizer_base<unwrap_party_key_t<DpfKey>>,
              std::decay_t<IntervalMemoizer>>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf,
    IntervalMemoizer && memoizer)
{
    auto outbufs = utils::make_tuple(
        make_output_buffer_for_full<I>(dpf),
        make_output_buffer_for_full<Is>(dpf)...);

    // moving `outbufs` is allowed as the `outbufs` are `std::vectors`
    //   the underlying data remains on the heap
    //   and thus the data the iterable refers to is still valid
    auto iterable = eval_full<I, Is...>(dpf, outbufs, memoizer);
    return std::make_pair(std::move(outbufs), std::move(iterable));
}

/// @brief Evaluate the whole domain, allocating a basic full memoizer and a buffer.
/// @tparam I output index
/// @tparam Is is
/// @tparam DpfKey DPF key type
/// @tparam DpfKey DPF key type
/// @param dpf the DPF key
/// @return the evaluation result
/// \complexity Same expansion as `eval_interval` on the whole domain. L = 2^{n - lg(outputs_per_leaf)} leaf nodes, n = `depth`. Time Θ(L) interior traversals. The output buffer stores one slot per domain point (2^n).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey> && !is_multilevel_key_v<DpfKey>, bool> = true>
HEDLEY_ALWAYS_INLINE
auto eval_full(const DpfKey & dpf)
{
    return eval_full<I, Is...>(dpf,
        dpf::make_basic_full_memoizer(dpf));
}

/// @brief Full-domain deferred eval while the input offset is unset.
/// @details Sugar for `defer_eval_interval` over `[min, max]`. `outbufs` must
///          be full-domain sized. After assign, `.get()` yields the logical
///          full-domain view (same values as eager `eval_full` after assign).
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          typename IntervalMemoizer,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey>
              && !is_multilevel_key_v<DpfKey>, bool> = true>
auto defer_eval_full(const DpfKey & dpf, OutputBuffers & outbufs,
    IntervalMemoizer && memoizer)  // NOLINT(runtime/references)
{
    using input_type = typename DpfKey::input_type;
    return defer_eval_interval<I, Is...>(dpf,
        std::numeric_limits<input_type>::min(),
        std::numeric_limits<input_type>::max(),
        outbufs, std::forward<IntervalMemoizer>(memoizer));
}

/// @brief `defer_eval_full` with a basic full-domain memoizer.
template <std::size_t I = 0,
          std::size_t ...Is,
          typename DpfKey,
          typename OutputBuffers,
          std::enable_if_t<looks_like_dpf_key_v<DpfKey>
              && !is_multilevel_key_v<DpfKey>, bool> = true,
          std::enable_if_t<!std::is_base_of_v<
              dpf::interval_memoizer_base<unwrap_party_key_t<DpfKey>>,
              std::decay_t<OutputBuffers>>, bool> = true>
auto defer_eval_full(const DpfKey & dpf, OutputBuffers & outbufs)  // NOLINT(runtime/references)
{
    return defer_eval_full<I, Is...>(dpf, outbufs,
        dpf::make_basic_full_memoizer(dpf));
}

}  // namespace dpf

#endif  // LIBDPF_INCLUDE_DPF_EVAL_FULL_HPP__