introspect.hpp

/*
 * This file is part of libtcspc
 * Copyright 2019-2026 Board of Regents of the University of Wisconsin System
 * SPDX-License-Identifier: MIT
 */
 
#pragma once
 
#include <algorithm>
#include <array>
#include <charconv>
#include <concepts>
#include <cstdint>
#include <cstdlib>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <string>
#include <typeindex>
#include <utility>
#include <vector>
 
#ifdef __GNUC__
#if __has_include(<cxxabi.h>)
#define LIBTCSPC_HAVE_CXA_DEMANGLE
#include <cxxabi.h>
#else
#warning introspected type names will be mangled (cxxabi.h not available)
#endif
#endif
 
namespace tcspc {
 
namespace internal {
 
[[nodiscard]] inline auto maybe_demangle(char const *mangled) -> std::string {
#ifdef LIBTCSPC_HAVE_CXA_DEMANGLE
    int status{-1};
    auto demangled = std::unique_ptr<char, void (*)(void *)>(
        abi::__cxa_demangle(mangled, nullptr, nullptr, &status), std::free);
    return status == 0 ? demangled.get() : mangled;
#else
    return mangled;
#endif
}
 
} // namespace internal

class processor_info {
    std::uintptr_t addr;
    std::type_index typ;
    std::string nm;
 
  public:
    template <typename Processor>
    explicit processor_info(Processor const *processor, std::string name)
        : addr(std::uintptr_t(processor)), typ(typeid(Processor)),
          nm(std::move(name)) {}

    [[nodiscard]] auto address() const -> std::uintptr_t { return addr; }

    [[nodiscard]] auto type_name() const -> std::string {
        return internal::maybe_demangle(typ.name());
    }

    [[nodiscard]] auto name() const -> std::string { return nm; }

    friend auto operator==(processor_info const &lhs,
                           processor_info const &rhs) -> bool = default;
};

class processor_node_id {
    // The processor address is not sufficient as a unique id, because some
    // processors have their downstream as the first data member (resulting in
    // the downstream having the same address). Pairing with the type id fixes
    // this issue, because a data member cannot have the same type as its
    // containing class.
    std::uintptr_t addr;
    std::type_index typ;
 
  public:
    template <typename Processor>
    explicit processor_node_id(Processor const *processor)
        : addr(std::uintptr_t(processor)), typ(typeid(Processor)) {}

    friend auto operator==(processor_node_id const &lhs,
                           processor_node_id const &rhs) -> bool = default;

    friend auto operator<(processor_node_id const &lhs,
                          processor_node_id const &rhs) -> bool {
        return lhs.addr < rhs.addr ||
               (lhs.addr == rhs.addr && lhs.typ < rhs.typ);
    }

    friend auto operator>(processor_node_id const &lhs,
                          processor_node_id const &rhs) -> bool {
        return lhs.addr > rhs.addr ||
               (lhs.addr == rhs.addr && lhs.typ > rhs.typ);
    }

    friend auto operator<=(processor_node_id const &lhs,
                           processor_node_id const &rhs) -> bool {
        return not(lhs > rhs);
    }

    friend auto operator>=(processor_node_id const &lhs,
                           processor_node_id const &rhs) -> bool {
        return not(lhs < rhs);
    }
};
 
class processor_graph; // forward declaration for introspectable

template <typename Proc>
concept introspectable = requires(Proc const &p) {
    { p.introspect_node() } -> std::same_as<processor_info>;
    { p.introspect_graph() } -> std::same_as<processor_graph>;
};

class processor_graph {
    struct node_type {
        processor_node_id id;
        processor_info info;
    };
 
    // All vectors kept sorted individually.
    std::vector<node_type> nds;
    std::vector<std::pair<processor_node_id, processor_node_id>> edgs;
    std::vector<processor_node_id> entrypts;
 
  public:
    template <typename Processor>
        requires introspectable<Processor>
    auto push_entry_point(Processor const *processor) -> processor_graph & {
        if (entrypts.size() > 1) {
            throw std::logic_error(
                "processor_graph can only push entry point when it has at most one entry point");
        }
 
        auto const id = processor_node_id(processor);
        auto node = node_type{id, processor->introspect_node()};
        auto [node_lower, node_upper] = std::equal_range(
            nds.begin(), nds.end(), node,
            [](auto const &l, auto const &r) { return l.id < r.id; });
        if (node_lower != node_upper) {
            throw std::logic_error(
                "processor_graph cannot push entry point that already exists");
        }
        nds.insert(node_upper, std::move(node));
 
        if (entrypts.empty()) {
            entrypts.push_back(id);
        } else {
            auto const edge = std::pair{id, entrypts[0]};
            auto edge_inspt = std::upper_bound(edgs.begin(), edgs.end(), edge);
            edgs.insert(edge_inspt, edge);
            entrypts[0] = id;
        }
 
        return *this;
    }

    [[nodiscard]] auto nodes() const -> std::vector<processor_node_id> {
        std::vector<processor_node_id> ret;
        ret.reserve(nds.size());
        std::transform(nds.begin(), nds.end(), std::back_inserter(ret),
                       [](auto const &n) { return n.id; });
        return ret;
    }

    [[nodiscard]] auto edges() const
        -> std::vector<std::pair<processor_node_id, processor_node_id>> {
        return edgs;
    }

    [[nodiscard]] auto entry_points() const -> std::vector<processor_node_id> {
        return entrypts;
    }

    [[nodiscard]] auto is_entry_point(processor_node_id id) const -> bool {
        return std::find(entrypts.begin(), entrypts.end(), id) !=
               entrypts.end();
    }

    [[nodiscard]] auto node_index(processor_node_id id) const -> std::size_t {
        auto it = std::find_if(nds.begin(), nds.end(),
                               [id](auto const &n) { return n.id == id; });
        if (it == nds.end())
            throw std::out_of_range("no such node id in processor_graph");
        return std::size_t(std::distance(nds.begin(), it));
    }

    [[nodiscard]] auto node_info(processor_node_id id) const
        -> processor_info {
        auto it = std::find_if(nds.begin(), nds.end(),
                               [id](auto const &n) { return n.id == id; });
        if (it == nds.end())
            throw std::out_of_range("no such node id in processor_graph");
        return it->info;
    }
 
    friend auto merge_processor_graphs(processor_graph const &a,
                                       processor_graph const &b)
        -> processor_graph;
};

[[nodiscard]] inline auto merge_processor_graphs(processor_graph const &a,
                                                 processor_graph const &b)
    -> processor_graph {
    processor_graph c;
 
    c.nds.reserve(a.nds.size() + b.nds.size());
    std::set_union(a.nds.begin(), a.nds.end(), b.nds.begin(), b.nds.end(),
                   std::back_inserter(c.nds),
                   [](auto const &l, auto const &r) { return l.id < r.id; });
 
    c.edgs.reserve(a.edgs.size() + b.edgs.size());
    std::set_union(a.edgs.begin(), a.edgs.end(), b.edgs.begin(), b.edgs.end(),
                   std::back_inserter(c.edgs));
 
    c.entrypts.reserve(a.entrypts.size() + b.entrypts.size());
    std::set_union(a.entrypts.begin(), a.entrypts.end(), b.entrypts.begin(),
                   b.entrypts.end(), std::back_inserter(c.entrypts));
 
    return c;
}
 
namespace internal {
 
inline auto format_hex_addr(std::uintptr_t p) -> std::string {
    std::array<char, sizeof(void *) * 2 + 3> buf{};
    std::fill(buf.begin(), buf.end(), '0');
    // NOLINTBEGIN(cppcoreguidelines-pro-bounds-pointer-arithmetic)
    auto const r =
        std::to_chars(buf.data(), buf.data() + buf.size() - 1, p, 16);
    *r.ptr = '\0';
    std::rotate(buf.begin(),
                std::next(buf.begin(), std::distance(buf.data(), r.ptr) + 1),
                buf.end());
    // NOLINTEND(cppcoreguidelines-pro-bounds-pointer-arithmetic)
    buf[1] = 'x';
    return buf.data();
};
 
} // namespace internal

[[nodiscard]] inline auto
graphviz_from_processor_graph(processor_graph const &graph) -> std::string {
    std::string dot;
    dot += "digraph G {\n";
    for (auto const &node : graph.nodes()) {
        processor_info const info = graph.node_info(node);
        dot += "    n";
        dot += std::to_string(graph.node_index(node));
        dot += " [shape=box label=\"";
        dot += info.name();
        dot += "\" tooltip=\"";
        dot += info.type_name();
        dot += " at ";
        dot += internal::format_hex_addr(info.address());
        dot += "\"];\n";
    }
    for (auto const &edge : graph.edges()) {
        dot += "    n";
        dot += std::to_string(graph.node_index(edge.first));
        dot += " -> n";
        dot += std::to_string(graph.node_index(edge.second));
        dot += ";\n";
    }
    dot += "}\n";
    return dot;
}
 
} // namespace tcspc