#include "Scene_Base.hpp"

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <memory_resource>
#include <queue>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include <taskflow/taskflow.hpp>

#include "renderive/renderable/Render_Frame_Completion.hpp"
#include "renderive/renderable/Renderive_Id_Allocator.hpp"
#include "renderive/renderable/base/Renderable_Base_p.hpp"
#include "renderive/renderable/color/Color_Cache.hpp"
#include "renderive/state/base/State_Strategy_Base.hpp"

static_assert(TF_VERSION == 400100, "Renderive requires Taskflow 4.1.0");

namespace {

bool contains_id(const std::vector<Renderable_Id>& values, Renderable_Id id) {
    return std::find(values.begin(), values.end(), id) != values.end();
}

bool contains_id(const std::pmr::vector<Renderable_Id>& values,
                 Renderable_Id id) {
    return std::find(values.begin(), values.end(), id) != values.end();
}

} // namespace

void Scene_Base::Id_Topology::erase_id(std::pmr::vector<Renderable_Id>& values, Renderable_Id id) noexcept {
    std::erase(values, id);
}
void Scene_Base::Id_Topology::validate_endpoint(Renderable_Id id) const {
    if (!nodes_.contains(id))
        throw std::invalid_argument("topology endpoint is not attached");
}
void Scene_Base::Id_Topology::attach(Renderable_Id id) {
    if (id == 0 || nodes_.contains(id))
        throw std::invalid_argument("topology node is already attached");
    nodes_.try_emplace(id, *nodes_.get_allocator().resource());
}
void Scene_Base::Id_Topology::erase(Renderable_Id id) {
    const auto iterator = nodes_.find(id);
    if (iterator == nodes_.end())
        return;
    if (!iterator->second.parents.empty() || !iterator->second.children.empty())
        throw std::logic_error("topology node still has relationships");
    nodes_.erase(iterator);
}
bool Scene_Base::Id_Topology::replace_parents(Renderable_Id child, const std::vector<Renderable_Id>& parents) {
    validate_endpoint(child);
    std::vector<Renderable_Id> unique;
    unique.reserve(parents.size());
    for (const Renderable_Id parent : parents) {
        validate_endpoint(parent);
        if (!contains_id(unique, parent))
            unique.push_back(parent);
    }
    auto& child_node = nodes_.at(child);
    if (child_node.parents.size() == unique.size() && std::all_of(unique.begin(), unique.end(), [&](Renderable_Id parent) {
        return contains_id(child_node.parents, parent);
    }))
        return false;
    const std::vector<Renderable_Id> previous(child_node.parents.begin(), child_node.parents.end());
    for (const Renderable_Id parent : previous)
        erase_id(nodes_.at(parent).children, child);
    child_node.parents.clear();
    child_node.parents.insert(child_node.parents.end(), unique.begin(), unique.end());
    for (const Renderable_Id parent : unique) {
        auto& children = nodes_.at(parent).children;
        if (!contains_id(children, child))
            children.push_back(child);
    }
    return true;
}
bool Scene_Base::Id_Topology::add_parent(Renderable_Id child, Renderable_Id parent) {
    validate_endpoint(child);
    validate_endpoint(parent);
    auto& child_node = nodes_.at(child);
    if (contains_id(child_node.parents, parent))
        return false;
    child_node.parents.push_back(parent);
    nodes_.at(parent).children.push_back(child);
    return true;
}
bool Scene_Base::Id_Topology::clear_parents(Renderable_Id child) {
    validate_endpoint(child);
    auto& child_node = nodes_.at(child);
    if (child_node.parents.empty())
        return false;
    const std::vector<Renderable_Id> parents(child_node.parents.begin(), child_node.parents.end());
    for (const Renderable_Id parent : parents)
        erase_id(nodes_.at(parent).children, child);
    child_node.parents.clear();
    return true;
}
bool Scene_Base::Id_Topology::contains(Renderable_Id id) const noexcept {
    return nodes_.contains(id);
}
bool Scene_Base::Id_Topology::isolated(Renderable_Id id) const {
    const auto& value = node(id);
    return value.parents.empty() && value.children.empty();
}
const Scene_Base::Topology_Node& Scene_Base::Id_Topology::node(Renderable_Id id) const {
    return nodes_.at(id);
}
std::vector<Renderable_Id> Scene_Base::Id_Topology::ids() const {
    std::vector<Renderable_Id> result;
    result.reserve(nodes_.size());
    for (const auto& [id, node] : nodes_) {
        static_cast<void>(node);
        result.push_back(id);
    }
    return result;
}
std::vector<Renderable_Id> Scene_Base::Id_Topology::order() const {
    std::unordered_map<Renderable_Id, std::size_t> indegree;
    indegree.reserve(nodes_.size());
    std::priority_queue<Renderable_Id, std::vector<Renderable_Id>, std::greater<>> ready;
    for (const auto& [id, node] : nodes_) {
        indegree.emplace(id, node.parents.size());
        if (node.parents.empty())
            ready.push(id);
    }
    std::vector<Renderable_Id> result;
    result.reserve(nodes_.size());
    while (!ready.empty()) {
        const Renderable_Id id = ready.top();
        ready.pop();
        result.push_back(id);
        for (const Renderable_Id child : nodes_.at(id).children) {
            auto& value = indegree.at(child);
            if (--value == 0)
                ready.push(child);
        }
    }
    if (result.size() != nodes_.size())
        throw std::logic_error("topology contains a cycle");
    return result;
}

class Scene_Base::Execution_Context {
public:
    static tf::Executor& executor() {
        static tf::Executor executor;
        return executor;
    }
};

class Scene_Base::Render_Execution_Scope {
public:
    explicit Render_Execution_Scope(Scene_Base& scene) noexcept
        : previous_(std::exchange(active_execution_scene_, &scene)) {}

    ~Render_Execution_Scope() {
        active_execution_scene_ = previous_;
    }

private:
    Scene_Base* previous_{};
};

Scene_Base::Scene_Base() : Scene_Base(*std::pmr::get_default_resource()) {}
Scene_Base::Scene_Base(std::pmr::memory_resource& upstream_memory_resource)
    : scene_lifetime_(std::make_shared<Scene_Lifetime>(*this)),
      memory_domain_(std::allocate_shared<Scene_Memory_Domain>(std::pmr::polymorphic_allocator<Scene_Memory_Domain>(&upstream_memory_resource), upstream_memory_resource)),
      renderables_(&memory_domain_->resource()),
      display_topology_(memory_domain_->resource()),
      dependency_topology_(memory_domain_->resource()),
      color_caches_(&memory_domain_->resource()),
      task_(memory_domain_->resource()),
      renderable_edit_queue_(&memory_domain_->resource()),
      composite_begin_node_id_(allocate_renderive_node_id()) {
    worker_ = std::thread([this] { render_loop(); });
}
Scene_Base::~Scene_Base() {
    shutdown();
}
Scene_Base::Attach_Builder::Attach_Builder(Scene_Base& scene)
    : scene_(scene), task_lock_(scene.task_mutex_), editor_(scene) {
    if (scene.runtime_started_)
        throw std::logic_error("scene attach builder is only available before runtime starts");
}
Scene_Base::Attach_Builder::~Attach_Builder() {
    try {
        std::lock_guard lock(scene_.model_mutex_);
        scene_.cleanup_detached_topology_locked();
        scene_.validate_structure_locked();
    } catch (...) {
        Scene_Base::structure_fail_fast("initial scene structure", std::current_exception());
    }
}
void Scene_Base::Attach_Builder::attach(Renderable renderable) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.attach(std::move(renderable));
}
void Scene_Base::Attach_Builder::set_display_parent(const Renderable& child, const Renderable& parent) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.set_display_parent(child, parent);
}
void Scene_Base::Attach_Builder::add_display_parent(const Renderable& child, const Renderable& parent) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.add_display_parent(child, parent);
}
void Scene_Base::Attach_Builder::clear_display_parent(const Renderable& child) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.clear_display_parent(child);
}
void Scene_Base::Attach_Builder::set_dependency_parent(const Renderable& child, const Renderable& parent) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.set_dependency_parent(child, parent);
}
void Scene_Base::Attach_Builder::add_dependency_parent(const Renderable& child, const Renderable& parent) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.add_dependency_parent(child, parent);
}
void Scene_Base::Attach_Builder::clear_dependency_parent(const Renderable& child) {
    std::lock_guard lock(scene_.model_mutex_);
    editor_.clear_dependency_parent(child);
}
Scene_Base::Attach_Builder Scene_Base::attach_builder() {
    return Attach_Builder(*this);
}
void Scene_Base::Renderable_Editor::attach(Renderable renderable) {
    if (!renderable)
        throw std::invalid_argument("renderable is null");
    renderable->d_func().bind_scene(scene_.scene_lifetime_);
    auto& renderable_data = renderable->d_func();
    const Renderable_Id id = renderable_data.renderable_id;
    if (const auto existing = scene_.renderables_.find(id);
        existing != scene_.renderables_.end()) {
        if (existing->second != renderable)
            throw std::logic_error("renderable id is already attached");
        return;
    }
    if (!scene_.display_topology_.contains(id))
        scene_.display_topology_.attach(id);
    if (!scene_.dependency_topology_.contains(id))
        scene_.dependency_topology_.attach(id);
    auto cache = scene_.make_renderable_color_cache();
    if (!scene_.renderables_.try_emplace(id, renderable).second)
        throw std::logic_error("renderable id is already attached");
    try {
        if (cache && !scene_.color_caches_.try_emplace(id, std::move(cache)).second)
            throw std::logic_error("renderable color cache is already attached");
    } catch (...) {
        scene_.renderables_.erase(id);
        throw;
    }
    renderable_data.real_time_data_state->attached.store(
        true, std::memory_order_release);
    renderable_data.invalidate_prepare();
    scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::detach(const Renderable& renderable) {
    if (!renderable)
        throw std::invalid_argument("renderable is null");
    scene_.validate_renderable_scene(*renderable);
    if (!scene_.is_renderable_attached_locked(renderable))
        return;
    auto& renderable_data = renderable->d_func();
    const Renderable_Id id = renderable_data.renderable_id;
    renderable_data.real_time_data_state->attached.store(
        false, std::memory_order_release);
    scene_.color_caches_.erase(id);
    scene_.renderables_.erase(id);
    scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::set_display_parent(const Renderable& child, const Renderable& parent) {
    if (!child || !parent)
        throw std::invalid_argument("display relationship endpoint is null");
    scene_.validate_renderable_scene(*child);
    scene_.validate_renderable_scene(*parent);
    if (scene_.display_topology_.replace_parents(
            child->d_func().renderable_id,
            {parent->d_func().renderable_id}))
        scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::add_display_parent(const Renderable& child, const Renderable& parent) {
    if (!child || !parent)
        throw std::invalid_argument("display relationship endpoint is null");
    scene_.validate_renderable_scene(*child);
    scene_.validate_renderable_scene(*parent);
    if (scene_.display_topology_.add_parent(child->d_func().renderable_id,
                                            parent->d_func().renderable_id))
        scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::clear_display_parent(const Renderable& child) {
    if (!child)
        throw std::invalid_argument("display child is null");
    scene_.validate_renderable_scene(*child);
    if (scene_.display_topology_.clear_parents(child->d_func().renderable_id))
        scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::set_dependency_parent(const Renderable& child, const Renderable& parent) {
    if (!child || !parent)
        throw std::invalid_argument("dependency relationship endpoint is null");
    scene_.validate_renderable_scene(*child);
    scene_.validate_renderable_scene(*parent);
    if (!scene_.dependency_topology_.replace_parents(
            child->d_func().renderable_id,
            {parent->d_func().renderable_id}))
        return;
    child->d_func().invalidate_prepare();
    scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::add_dependency_parent(const Renderable& child, const Renderable& parent) {
    if (!child || !parent)
        throw std::invalid_argument("dependency relationship endpoint is null");
    scene_.validate_renderable_scene(*child);
    scene_.validate_renderable_scene(*parent);
    if (!scene_.dependency_topology_.add_parent(child->d_func().renderable_id,
                                                parent->d_func().renderable_id))
        return;
    child->d_func().invalidate_prepare();
    scene_.notify_model_dirty();
}
void Scene_Base::Renderable_Editor::clear_dependency_parent(const Renderable& child) {
    if (!child)
        throw std::invalid_argument("dependency child is null");
    scene_.validate_renderable_scene(*child);
    if (!scene_.dependency_topology_.clear_parents(child->d_func().renderable_id))
        return;
    child->d_func().invalidate_prepare();
    scene_.notify_model_dirty();
}
void Scene_Base::edit_renderables(Renderable_Edit edit) {
    if (!edit)
        throw std::invalid_argument("renderable edit callback is empty");
    enqueue_renderable_edit(std::move(edit));
}
void Scene_Base::render() {
    submit_render(nullptr);
}

void Scene_Base::render(Abstract_Frame& frame) {
    submit_render(&frame);
}

void Scene_Base::submit_render(Abstract_Frame* frame) {
    if (active_submitted_observer_scene_ == this) {
        std::lock_guard<std::recursive_mutex> lock(task_mutex_);
        ++deferred_render_count_;
        return;
    }
    auto task_lock = lock_render_idle();
    runtime_started_ = true;
    if (pending_exception_observed_) {
        pending_exception_ = nullptr;
        pending_exception_observed_ = false;
    }
    if (!pending_exception_ && current_completion_ &&
        current_completion_->completed && current_completion_->exception &&
        !current_completion_->observed) {
        pending_exception_ = current_completion_->exception;
    }

    auto& strategy = frame_control_strategy();
    strategy.swap();
    auto snapshot = snapshot_live_model();
    snapshot->next_refresh_interval_ns_ =
        strategy.frame_control_state().next_refresh_interval_ns;
    snapshot->scene_state_revision_ = acquire_scene_state();
    if (render_sequence_ == std::numeric_limits<std::uint64_t>::max())
        throw std::overflow_error("render sequence exhausted");
    snapshot->render_sequence = ++render_sequence_;
    snapshot->viewport = frame_viewport();

    Render_Task task(memory_resource());
    task.frame = frame
        ? Render_Task::Frame{std::ref(*frame)}
        : Render_Task::Frame{std::make_shared<Abstract_Frame>()};
    task.plan = compile_render_plan(*snapshot, task);
    task.completion = std::make_shared<Render_Completion>();
    snapshot->capture_ticket_ = capture_controller_.begin_frame();
    task.snapshot = std::move(snapshot);
    current_completion_ = task.completion;
    const Observation submitted_observation{
        Observation_Event::render_submitted, observer_now_ns(),
        task.snapshot->render_sequence, task.snapshot->scene_state_revision_,
        task.snapshot->renderables.size()};
    task_ = std::move(task);
    task_pending_ = true;
    task_lock.unlock();

    Scene_Base* previous_observer_scene =
        std::exchange(active_submitted_observer_scene_, this);
    observe_scene(submitted_observation);
    active_submitted_observer_scene_ = previous_observer_scene;
    task_ready_.notify_one();

    std::size_t deferred_render_count{};
    {
        std::lock_guard<std::recursive_mutex> lock(task_mutex_);
        deferred_render_count = std::exchange(deferred_render_count_, 0);
    }
    for (std::size_t index = 0; index < deferred_render_count; ++index)
        render();
}

void Scene_Base::wait_for_render() {
    if (is_render_worker_thread() || active_submitted_observer_scene_ == this)
        return;
    std::unique_lock<std::recursive_mutex> lock(task_mutex_);
    const auto completion = current_completion_;
    if (!completion)
        return;
    render_completed_.wait(lock, [&completion] { return completion->completed; });
    std::exception_ptr exception;
    if (pending_exception_) {
        exception = pending_exception_;
        pending_exception_observed_ = true;
        if (!completion->exception)
            completion->observed = true;
    } else {
        exception = completion->exception;
        completion->observed = true;
    }
    lock.unlock();
    if (exception)
        std::rethrow_exception(exception);
}
void Scene_Base::enqueue_renderable_edit(Renderable_Edit edit) {
    std::lock_guard<std::recursive_mutex> lock(task_mutex_);
    enqueue_renderable_edit_locked(std::move(edit));
}
void Scene_Base::enqueue_renderable_edit_locked(Renderable_Edit edit) {
    if (stop_)
        throw std::logic_error("scene is shutting down");
    runtime_started_ = true;
    renderable_edit_queue_.push_back({std::move(edit)});
    task_ready_.notify_one();
}
void Scene_Base::cleanup_detached_topology_locked() {
    const auto cleanup = [this](Id_Topology& topology, const char* name) {
        for (const Renderable_Id id : topology.ids()) {
            if (renderables_.contains(id))
                continue;
            if (!topology.isolated(id))
                throw std::logic_error(std::string(name) + " topology still references detached renderable " + std::to_string(id));
            topology.erase(id);
        }
    };
    cleanup(display_topology_, "display");
    cleanup(dependency_topology_, "dependency");
}
void Scene_Base::validate_structure_locked() {
    for (const auto& [id, renderable] : renderables_) {
        if (!renderable)
            throw std::logic_error("scene contains null renderable owner");
        validate_renderable_scene(*renderable);
        if (!renderable->d_func().real_time_data_state->attached.load(
                std::memory_order_acquire))
            throw std::logic_error("scene contains renderable whose attached state is false");
        if (!display_topology_.contains(id))
            throw std::logic_error("display topology is missing attached renderable " + std::to_string(id));
        if (!dependency_topology_.contains(id))
            throw std::logic_error("dependency topology is missing attached renderable " + std::to_string(id));
    }
    const auto validate_topology = [this](const Id_Topology& topology, const char* name) {
        const auto order = topology.order();
        if (order.size() != renderables_.size())
            throw std::logic_error(std::string(name) + " topology does not match attached renderables");
        for (const Renderable_Id id : order) {
            if (!renderables_.contains(id))
                throw std::logic_error(std::string(name) + " topology references detached renderable " + std::to_string(id));
        }
    };
    validate_topology(display_topology_, "display");
    validate_topology(dependency_topology_, "dependency");
}
[[noreturn]] void Scene_Base::structure_fail_fast(const char* stage, std::exception_ptr exception) noexcept {
    std::fprintf(stderr, "Renderive scene structure failure during %s", stage ? stage : "unknown stage");
    if (exception) {
        try {
            std::rethrow_exception(exception);
        } catch (const std::exception& value) {
            std::fprintf(stderr, ": %s", value.what());
        } catch (...) {
            std::fprintf(stderr, ": unknown exception");
        }
    }
    std::fprintf(stderr, "\n");
    std::fflush(stderr);
    std::abort();
}
void Scene_Base::request_render_graph_rebuild(Renderable_Base& renderable) {
    auto& renderable_data = renderable.d_func();
    if (!renderable_data.real_time_data_state->attached.load(
            std::memory_order_acquire)) {
        renderable_data.reset_render_graph();
        return;
    }
    validate_renderable_scene(renderable);
    if (active_renderable_edit_scene_ == this) {
        renderable_data.reset_render_graph();
        notify_model_dirty();
        return;
    }
    Renderable owner;
    {
        std::lock_guard lock(model_mutex_);
        const auto iterator = renderables_.find(renderable_data.renderable_id);
        if (iterator == renderables_.end() || iterator->second.get() != &renderable)
            return;
        owner = iterator->second;
    }
    std::lock_guard<std::recursive_mutex> lock(task_mutex_);
    if (!runtime_started_) {
        owner->d_func().reset_render_graph();
        notify_model_dirty();
        return;
    }
    enqueue_renderable_edit_locked([owner = std::move(owner)](Renderable_Editor&) {
        owner->d_func().reset_render_graph();
        owner->d_func().notify_scene_model_dirty();
    });
}
void Scene_Base::publish_frame_state() {
    auto task_lock = lock_render_idle();
    if (auto* state = dynamic_cast<State_Strategy_Base*>(this))
        state->publish();
    std::vector<Renderable> renderables;
    {
        std::lock_guard lock(model_mutex_);
        renderables.reserve(renderables_.size());
        for (const auto& [id, renderable] : renderables_) {
            static_cast<void>(id);
            renderables.push_back(renderable);
        }
    }
    for (const Renderable& renderable : renderables) {
        if (auto* state = dynamic_cast<State_Strategy_Base*>(renderable.get()))
            state->publish();
        renderable->d_func().publish_real_time_data();
    }
}

void Scene_Base::notify_model_dirty() noexcept {
    model_dirty_.store(true, std::memory_order_release);
}

void Scene_Base::invalidate_renderables() {
    std::lock_guard lock(model_mutex_);
    for (const auto& [id, renderable] : renderables_) {
        static_cast<void>(id);
        renderable->d_func().invalidate_prepare();
    }
    notify_model_dirty();
}

std::size_t Scene_Base::renderable_count() const {
    std::lock_guard lock(model_mutex_);
    return renderables_.size();
}

Scene_Base::Topology_Snapshot Scene_Base::topology_snapshot() const {
    std::lock_guard lock(model_mutex_);
    Topology_Snapshot snapshot;
    const auto ids = display_topology_.order();
    snapshot.renderables.reserve(ids.size());
    snapshot.display.reserve(ids.size());
    snapshot.dependency.reserve(ids.size());
    for (const Renderable_Id id : ids)
        snapshot.renderables.push_back(renderables_.at(id));
    const auto append_relationships = [&](const Id_Topology& topology,
                                          auto& output) {
        for (const Renderable_Id id : ids) {
            const auto& parents = topology.node(id).parents;
            if (parents.empty()) {
                output.push_back({renderables_.at(id), {}});
                continue;
            }
            for (const Renderable_Id parent : parents)
                output.push_back({renderables_.at(id), renderables_.at(parent)});
        }
    };
    append_relationships(display_topology_, snapshot.display);
    append_relationships(dependency_topology_, snapshot.dependency);
    return snapshot;
}

std::vector<Scene_Base::Const_Renderable> Scene_Base::paint_order_snapshot() const {
    std::lock_guard lock(model_mutex_);
    std::vector<Const_Renderable> result;
    for (const Renderable_Id id : display_topology_.order())
        result.push_back(renderables_.at(id));
    return result;
}

std::shared_ptr<Frame_Render_Snapshot> Scene_Base::snapshot_live_model() {
    auto snapshot = std::make_shared<Frame_Render_Snapshot>();
    std::lock_guard lock(model_mutex_);
    const auto dependency_order = dependency_topology_.order();
    snapshot->display_order = display_topology_.order();
    snapshot->renderables.reserve(dependency_order.size());
    for (const Renderable_Id id : dependency_order) {
        const Renderable& owner = renderables_.at(id);
        auto& renderable_data = owner->d_func();
        Renderable_Frame_State state;
        state.renderable_id = id;
        state.visible = renderable_data.visible.load(std::memory_order_acquire);
        state.configuration = renderable_data.configuration.load(
            std::memory_order_acquire);
        state.prepare_revision = renderable_data.prepare_revision.load(
            std::memory_order_acquire);
        state.prepared_revision = renderable_data.prepared_revision.load(
            std::memory_order_acquire);
        state.paint_revision = renderable_data.paint_revision.load(
            std::memory_order_acquire);
        state.painted_revision = renderable_data.painted_revision.load(
            std::memory_order_acquire);
        state.painted_prepare_revision =
            renderable_data.painted_prepare_revision.load(
                std::memory_order_acquire);
        const bool prepare_valid =
            state.prepare_revision != std::numeric_limits<std::uint64_t>::max() &&
            state.configuration.cache_enabled &&
            state.prepared_revision == state.prepare_revision;
        const bool paint_valid =
            state.paint_revision != std::numeric_limits<std::uint64_t>::max() &&
            prepare_valid && state.painted_revision == state.paint_revision &&
            state.painted_prepare_revision == state.prepared_revision;
        state.prepare_required = !prepare_valid;
        state.paint_required = !paint_valid;
        state.render_graph = renderable_data.render_graph_snapshot();
        const auto& parents = dependency_topology_.node(id).parents;
        state.dependency_parent_ids.assign(parents.begin(), parents.end());
        state.owner_ = owner;
        if (const auto cache = color_caches_.find(id);
            cache != color_caches_.end())
            state.paint_buffer_ = cache->second;
        snapshot->renderables.push_back(std::move(state));
    }

    std::unordered_map<Renderable_Id, std::size_t> indices;
    indices.reserve(snapshot->renderables.size());
    std::unordered_map<Renderable_Id, std::vector<Renderable_Id>> children;
    children.reserve(snapshot->renderables.size());
    for (std::size_t index = 0; index < snapshot->renderables.size(); ++index) {
        const auto& state = snapshot->renderables[index];
        indices.emplace(state.renderable_id, index);
        children.try_emplace(state.renderable_id);
    }
    for (const auto& state : snapshot->renderables) {
        for (const Renderable_Id parent : state.dependency_parent_ids)
            children.at(parent).push_back(state.renderable_id);
    }
    std::vector<Renderable_Id> dirty;
    dirty.reserve(snapshot->renderables.size());
    for (const auto& state : snapshot->renderables) {
        if (state.prepare_required)
            dirty.push_back(state.renderable_id);
    }
    for (std::size_t cursor = 0; cursor < dirty.size(); ++cursor) {
        for (const Renderable_Id child : children.at(dirty[cursor])) {
            auto& state = snapshot->renderables.at(indices.at(child));
            if (state.prepare_required)
                continue;
            state.prepare_required = true;
            state.paint_required = true;
            dirty.push_back(child);
        }
    }
    return snapshot;
}

std::shared_ptr<const Render_Plan> Scene_Base::render_plan_snapshot() const {
    return render_plan_history_.current();
}

std::shared_ptr<const Render_Plan> Scene_Base::find_render_plan(
    Render_Plan_Version version) const {
    return render_plan_history_.find(version);
}

Capture_Session_Id Scene_Base::capture_next_frame() {
    return capture_frames(1);
}

Capture_Session_Id Scene_Base::capture_frames(std::size_t count) {
    std::lock_guard lock(task_mutex_);
    const Capture_Session_Id session_id = capture_controller_.capture_frames(count);
    capture_repository_.begin_session(session_id, count);
    return session_id;
}

Capture_Controller_State Scene_Base::capture_state() const noexcept {
    return capture_controller_.state();
}

std::optional<Capture_Session> Scene_Base::capture_session(
    Capture_Session_Id session_id) const {
    return capture_repository_.session(session_id);
}

std::vector<Capture_Session_Id> Scene_Base::capture_sessions() const {
    return capture_repository_.sessions();
}

std::vector<Node_Statistics> Scene_Base::node_statistics(
    Capture_Session_Id session_id) const {
    const auto captured = capture_repository_.session(session_id);
    if (!captured)
        return {};
    std::vector<Frame_Analysis> analyses;
    analyses.reserve(captured->frames.size());
    for (const auto& frame : captured->frames)
        analyses.push_back(frame.analysis);
    return analyze_node_statistics(analyses);
}

std::vector<Plan_Version_Statistics> Scene_Base::plan_version_statistics(
    Capture_Session_Id session_id) const {
    const auto captured = capture_repository_.session(session_id);
    if (!captured)
        return {};
    std::vector<Frame_Analysis> analyses;
    analyses.reserve(captured->frames.size());
    for (const auto& frame : captured->frames)
        analyses.push_back(frame.analysis);
    return analyze_plan_versions(analyses);
}

std::size_t Scene_Base::task_executor_worker_count() noexcept {
    return Execution_Context::executor().num_workers();
}

std::pmr::memory_resource& Scene_Base::memory_resource() const noexcept {
    return memory_domain_->resource();
}

std::pmr::memory_resource& Scene_Base::upstream_memory_resource() const noexcept {
    return memory_domain_->upstream();
}

Frame_Control_Strategy_Base& Scene_Base::frame_control_strategy() {
    return frame_control_strategy_impl();
}

const Frame_Control_Strategy_Base& Scene_Base::frame_control_strategy() const {
    return frame_control_strategy_impl();
}

Frame_Control_Strategy_Base& Scene_Base::frame_control_strategy_impl() {
    throw std::logic_error("frame control strategy is not available");
}

const Frame_Control_Strategy_Base& Scene_Base::frame_control_strategy_impl() const {
    throw std::logic_error("frame control strategy is not available");
}

std::shared_ptr<Color_Cache> Scene_Base::make_renderable_color_cache() {
    return {};
}

Frame_Viewport Scene_Base::frame_viewport() const {
    return {};
}

std::uint64_t Scene_Base::acquire_scene_state() {
    return 0;
}

void Scene_Base::observe_scene(const Observation&) noexcept {}

std::uint64_t Scene_Base::observer_now_ns() const noexcept {
    return 0;
}

std::unique_lock<std::recursive_mutex> Scene_Base::lock_render_idle() {
    if (is_render_worker_thread())
        throw std::logic_error(
            "render-idle operation is not allowed during render execution");
    if (active_submitted_observer_scene_ == this)
        throw std::logic_error(
            "render-idle operation is not allowed during render submission observation");
    std::unique_lock<std::recursive_mutex> lock(task_mutex_);
    render_completed_.wait(lock, [this] {
        return !task_pending_ && !rendering_ && renderable_edit_queue_.empty() && !editing_renderables_;
    });
    return lock;
}

bool Scene_Base::is_render_worker_thread() const noexcept {
    return active_execution_scene_ == this ||
           (worker_.joinable() &&
            std::this_thread::get_id() == worker_.get_id());
}

bool Scene_Base::consume_model_dirty() noexcept {
    return model_dirty_.exchange(false, std::memory_order_acq_rel);
}

void Scene_Base::shutdown() noexcept {
    {
        std::unique_lock<std::recursive_mutex> lock(task_mutex_);
        render_completed_.wait(lock, [this] {
            return !task_pending_ && !rendering_ && renderable_edit_queue_.empty() && !editing_renderables_;
        });
        stop_ = true;
    }
    task_ready_.notify_one();
    if (worker_.joinable())
        worker_.join();
    {
        std::lock_guard lock(model_mutex_);
        for (const auto& [id, renderable] : renderables_) {
            static_cast<void>(id);
            renderable->d_func().real_time_data_state->attached.store(
                false, std::memory_order_release);
        }
    }
    scene_lifetime_->invalidate();
}

void Scene_Base::render_loop() {
    for (;;) {
        Render_Task task(memory_resource());
        std::vector<Renderable_Edit_Command> edits;
        {
            std::unique_lock<std::recursive_mutex> lock(task_mutex_);
            task_ready_.wait(lock, [this] {
                return stop_ || task_pending_ || !renderable_edit_queue_.empty();
            });
            if (stop_)
                return;
            if (task_pending_) {
                task = std::move(task_);
                task_pending_ = false;
                rendering_ = true;
            } else {
                editing_renderables_ = true;
                edits.reserve(renderable_edit_queue_.size());
                while (!renderable_edit_queue_.empty()) {
                    edits.push_back(std::move(renderable_edit_queue_.front()));
                    renderable_edit_queue_.pop_front();
                }
            }
        }
        if (!edits.empty()) {
            {
                std::lock_guard lock(model_mutex_);
                Scene_Base* previous = std::exchange(active_renderable_edit_scene_, this);
                Renderable_Editor editor(*this);
                for (auto& command : edits) {
                    try {
                        command.edit(editor);
                        cleanup_detached_topology_locked();
                        validate_structure_locked();
                    } catch (...) {
                        active_renderable_edit_scene_ = previous;
                        structure_fail_fast("runtime renderable edit", std::current_exception());
                    }
                }
                active_renderable_edit_scene_ = previous;
            }
            {
                std::lock_guard<std::recursive_mutex> lock(task_mutex_);
                editing_renderables_ = false;
            }
            render_completed_.notify_all();
            continue;
        }
        const auto& snapshot = *task.snapshot;
        observe_scene({Observation_Event::render_started, observer_now_ns(),
                       snapshot.render_sequence,
                       snapshot.scene_state_revision_,
                       snapshot.renderables.size()});
        std::exception_ptr exception;
        try {
            execute_taskflow(task);
            observe_scene({Observation_Event::render_completed, observer_now_ns(),
                           snapshot.render_sequence,
                           snapshot.scene_state_revision_,
                           snapshot.renderables.size()});
        } catch (...) {
            exception = std::current_exception();
            observe_scene({Observation_Event::render_failed, observer_now_ns(),
                           snapshot.render_sequence,
                           snapshot.scene_state_revision_,
                           snapshot.renderables.size()});
        }
        {
            std::lock_guard lock(task_mutex_);
            task.completion->exception = exception;
            task.completion->completed = true;
            rendering_ = false;
        }
        render_completed_.notify_all();
    }
}

std::shared_ptr<const Render_Plan> Scene_Base::compile_render_plan(
    const Frame_Render_Snapshot& snapshot, Render_Task& task) {
    struct Active_Renderable {
        std::size_t snapshot_index{};
        std::vector<Render_Node_Id> prepare_roots;
        std::vector<Render_Node_Id> prepare_terminals;
        std::vector<Render_Node_Id> paint_terminals;
    };

    std::vector<Active_Renderable> active(snapshot.renderables.size());
    std::unordered_map<Renderable_Id, std::size_t> indices;
    indices.reserve(snapshot.renderables.size());
    for (std::size_t index = 0; index < snapshot.renderables.size(); ++index) {
        active[index].snapshot_index = index;
        indices.emplace(snapshot.renderables[index].renderable_id, index);
    }

    Render_Graph graph;
    std::unordered_map<Render_Node_Id, Execution_Binding> functions;
    const auto append_edge = [&graph](Render_Node_Id from, Render_Node_Id to) {
        if (from == 0 || to == 0 || from == to)
            return;
        const Render_Edge edge{from, to};
        if (std::find(graph.edges.begin(), graph.edges.end(), edge) ==
            graph.edges.end())
            graph.edges.push_back(edge);
    };

    for (auto& item : active) {
        const auto& state = snapshot.renderables[item.snapshot_index];
        if (!state.render_graph)
            throw std::logic_error("frame renderable has no graph snapshot");
        std::unordered_set<Render_Node_Id> selected;
        for (const auto& node : state.render_graph->graph.nodes) {
            if (node.kind == Render_Node_Kind::composite)
                throw std::logic_error(
                    "renderable graph must not define composite nodes");
            const bool include = node.kind == Render_Node_Kind::prepare
                ? state.prepare_required
                : state.paint_required;
            if (!include)
                continue;
            graph.nodes.push_back(node);
            const auto& render_function =
                state.render_graph->functions.at(node.execution_index);
            std::visit([&](const auto& function) {
                functions.emplace(node.node_id,
                    Execution_Binding{state.owner_, item.snapshot_index,
                                      Execution_Function{function}});
            }, render_function);
            selected.insert(node.node_id);
        }
        for (const auto& edge : state.render_graph->graph.edges) {
            if (selected.contains(edge.from) && selected.contains(edge.to))
                append_edge(edge.from, edge.to);
        }
        const auto stage_boundary = [&](Render_Node_Kind kind, bool roots) {
            std::vector<Render_Node_Id> result;
            if ((kind == Render_Node_Kind::prepare &&
                 !state.prepare_required) ||
                (kind == Render_Node_Kind::paint && !state.paint_required))
                return result;
            for (const auto& node : state.render_graph->graph.nodes) {
                if (node.kind != kind || !selected.contains(node.node_id))
                    continue;
                const bool connected = std::any_of(
                    state.render_graph->graph.edges.begin(),
                    state.render_graph->graph.edges.end(),
                    [&](const Render_Edge& edge) {
                        const Render_Node_Id adjacent =
                            roots ? edge.from : edge.to;
                        const bool matches = roots ? edge.to == node.node_id
                                                  : edge.from == node.node_id;
                        if (!matches || !selected.contains(adjacent))
                            return false;
                        return std::any_of(
                            state.render_graph->graph.nodes.begin(),
                            state.render_graph->graph.nodes.end(),
                            [&](const Render_Node& candidate) {
                                return candidate.node_id == adjacent &&
                                       candidate.kind == kind;
                            });
                    });
                if (!connected)
                    result.push_back(node.node_id);
            }
            return result;
        };
        item.prepare_roots =
            stage_boundary(Render_Node_Kind::prepare, true);
        item.prepare_terminals =
            stage_boundary(Render_Node_Kind::prepare, false);
        item.paint_terminals =
            stage_boundary(Render_Node_Kind::paint, false);
    }

    for (const auto& child : active) {
        const auto& child_state =
            snapshot.renderables[child.snapshot_index];
        for (const Renderable_Id parent_id :
             child_state.dependency_parent_ids) {
            const auto parent = indices.find(parent_id);
            if (parent == indices.end())
                continue;
            for (const Render_Node_Id parent_terminal :
                 active[parent->second].prepare_terminals) {
                for (const Render_Node_Id child_root : child.prepare_roots)
                    append_edge(parent_terminal, child_root);
            }
        }
    }

    if (auto* compositor = dynamic_cast<Scene_Compositor*>(this)) {
        graph.nodes.push_back({composite_begin_node_id_, 0, "Composite Frame",
                               Render_Node_Kind::composite, 0});
        functions.emplace(composite_begin_node_id_,
            Execution_Binding{{}, std::nullopt,
                Composite_Render_Node_Function{
                    [compositor](const Composite_Render_Context& context) {
                        compositor->begin_composite(context);
                    }}});
        Render_Node_Id previous = composite_begin_node_id_;
        for (const Renderable_Id id : snapshot.display_order) {
            const std::size_t index = indices.at(id);
            const auto& state = snapshot.renderables[index];
            const Render_Node_Id composite_node_id =
                state.owner_->d_func().composite_node_id;
            graph.nodes.push_back({composite_node_id, id,
                                   "Composite", Render_Node_Kind::composite, 0});
            functions.emplace(composite_node_id,
                Execution_Binding{state.owner_, index,
                    Composite_Render_Node_Function{
                        [compositor](const Composite_Render_Context& context) {
                            compositor->composite(context);
                        }}});
            append_edge(previous, composite_node_id);
            previous = composite_node_id;
            for (const Render_Node_Id paint : active[index].paint_terminals)
                append_edge(paint, composite_node_id);
        }
    }

    auto plan = render_plan_history_.publish(std::move(graph));
    task.execution_bindings.clear();
    task.execution_bindings.resize(plan->graph.nodes.size());
    for (const auto& node : plan->graph.nodes) {
        auto function = functions.find(node.node_id);
        if (function == functions.end())
            throw std::logic_error(
                "render plan node has no execution binding");
        task.execution_bindings[node.execution_index] =
            std::move(function->second);
    }
    return plan;
}

void Scene_Base::execute_taskflow(Render_Task& task) {
    Abstract_Frame* const frame = std::visit(
        []<class Frame>(Frame& value) -> Abstract_Frame* {
            if constexpr (std::same_as<Frame, std::shared_ptr<Abstract_Frame>>)
                return value.get();
            else
                return &value.get();
        },
        task.frame);
    if (!task.snapshot || !task.plan || !frame)
        throw std::logic_error("render task is incomplete");
    const auto& snapshot = *task.snapshot;
    const Capture_Frame_Ticket capture_ticket = snapshot.capture_ticket_;
    bool frame_active{};
    try {
        for (const auto& state : snapshot.renderables) {
            if (state.paint_required && state.paint_buffer_)
                state.paint_buffer_->clear();
        }

        tf::Taskflow taskflow;
        std::vector<tf::Task> tasks;
        tasks.reserve(task.plan->graph.nodes.size());
        const bool capture = capture_ticket.capture;
        frame->begin_render(snapshot.render_sequence, *task.plan, capture,
                            capture ? render_clock_now_ns() : 0);
        frame_active = true;
        for (const auto& node : task.plan->graph.nodes) {
            tasks.push_back(taskflow.emplace([
                this, &task, &snapshot, frame, node
            ](tf::Runtime& runtime) {
                Node_Execution* execution =
                    frame->execution_slot(node.execution_index);
                Node_Execution_Metrics* metrics =
                    execution ? &execution->metrics : nullptr;
                const auto run = [&] {
                    const auto& binding =
                        task.execution_bindings.at(node.execution_index);
                    switch (node.kind) {
                    case Render_Node_Kind::prepare: {
                        const auto& state = snapshot.renderables.at(
                            binding.renderable_index.value());
                        std::get<Prepare_Render_Node_Function>(binding.function)(
                            Prepare_Render_Context{snapshot, state, metrics});
                        break;
                    }
                    case Render_Node_Kind::paint: {
                        const auto& state = snapshot.renderables.at(
                            binding.renderable_index.value());
                        if (!state.paint_buffer_)
                            throw std::logic_error(
                                "paint node has no frame color cache");
                        std::get<Paint_Render_Node_Function>(binding.function)(
                            Paint_Render_Context{snapshot, state,
                                                 *state.paint_buffer_, metrics});
                        break;
                    }
                    case Render_Node_Kind::composite: {
                        const Renderable_Frame_State* state =
                            binding.renderable_index
                                ? &snapshot.renderables.at(
                                      *binding.renderable_index)
                                : nullptr;
                        const Color_Cache* cache =
                            state && state->paint_buffer_
                                ? state->paint_buffer_.get()
                                : nullptr;
                        std::get<Composite_Render_Node_Function>(binding.function)(
                            Composite_Render_Context{snapshot, state, cache,
                                                     metrics});
                        break;
                    }
                    }
                };
                if (!execution) {
                    Render_Execution_Scope scope(*this);
                    run();
                    return;
                }
                execution->worker_id =
                    static_cast<std::uint32_t>(runtime.worker().id());
                execution->start_time_ns = render_clock_now_ns();
                execution->status = Node_Execution_Status::running;
                Render_Execution_Scope scope(*this);
                try {
                    run();
                    execution->end_time_ns = render_clock_now_ns();
                    execution->status = Node_Execution_Status::complete;
                } catch (...) {
                    execution->end_time_ns = render_clock_now_ns();
                    execution->status = Node_Execution_Status::failed;
                    throw;
                }
            }).name(node.name));
        }
        std::unordered_map<Render_Node_Id, std::size_t> node_indices;
        node_indices.reserve(task.plan->graph.nodes.size());
        for (const auto& node : task.plan->graph.nodes)
            node_indices.emplace(node.node_id, node.execution_index);
        for (const auto& edge : task.plan->graph.edges)
            tasks.at(node_indices.at(edge.from))
                .precede(tasks.at(node_indices.at(edge.to)));
        Execution_Context::executor().run(taskflow).get();

        for (const auto& state : snapshot.renderables) {
            if (state.prepare_required)
                state.owner_->d_func().mark_prepared(state.prepare_revision);
            if (state.paint_required)
                state.owner_->d_func().mark_painted(state.paint_revision,
                                                    state.prepare_revision);
        }
        const auto completed = frame->complete_render(
            capture ? render_clock_now_ns() : 0);
        frame_active = false;
        for (const auto& state : snapshot.renderables) {
            if (!state.paint_required)
                continue;
            if (auto* completion = dynamic_cast<Render_Frame_Completion*>(
                    state.owner_.get())) {
                completion->render_frame_completed(
                    snapshot.next_refresh_interval_ns_);
            }
        }
        if (completed) {
            capture_repository_.publish(
                capture_ticket.session_id, completed,
                analyze_frame(*task.plan, *completed));
        }
        capture_controller_.finish_frame(capture_ticket, true);
    } catch (...) {
        if (frame_active)
            frame->discard_render();
        capture_controller_.finish_frame(capture_ticket, false);
        throw;
    }
}

void Scene_Base::validate_renderable_scene(
    const Renderable_Base& renderable) const {
    if (renderable.d_func().real_time_data_state->scene_lifetime.get() !=
        scene_lifetime_.get())
        throw std::invalid_argument("renderable belongs to another scene");
}

bool Scene_Base::is_renderable_attached_locked(
    const Renderable& renderable) const {
    if (!renderable)
        return false;
    const auto iterator = renderables_.find(renderable->d_func().renderable_id);
    return iterator != renderables_.end() &&
           iterator->second.get() == renderable.get();
}
