Unable to specify a class methods as constexpr in C++

Question

Edit: I want to convert a string to DFA, which will be std::array<std::array<int, ...>, ...>. This should be computable at compile time without any problems, as the output type can be returned from constexpr functions. I am stuck on how to do this with the intermediate step of allocating memory and deallocating it at other places (string to NFA and NFA to DFA algorithm)

I am writing a simple compile time regex parser in C++ using constexpr functions (string -> NFA -> DFA). But, I am unable to make some of my class methods as constexpr. I tried various combination, but it seems I have to implement my own version of std::shared_ptr which is constexpr for each member function.

Can someone help me here? This seems a trivial problem as new and delete have constexpr support now and I am still unable to declare my methods constexpr. Here is the code:

#include <memory>
#include <variant>
#include <iostream>
#include <utility>
#include <cstdint>
#include <vector>
#include <bit>
#include <source_location>
#include <array>
#include <string_view>
#include <algorithm>
#include <type_traits>
#include <limits>

struct Node
{
private:
    friend class NodeManager;
    std::size_t unique_index{ std::numeric_limits<std::size_t>::max() };
public:
    std::vector<std::shared_ptr<Node>> empty_transitions{};
    std::vector<std::pair<std::string, std::shared_ptr<Node>>> tran_nodes{};
};

class NodeManager
{
public:
    constexpr NodeManager() = default;
    constexpr NodeManager(const NodeManager&) = delete;
    constexpr NodeManager(NodeManager&&) = delete;
    constexpr NodeManager& operator=(const NodeManager&) = delete;
    constexpr NodeManager& operator=(NodeManager&&) = delete;

    std::vector<std::shared_ptr<Node>> all_nodes;

    constexpr auto create_node() -> std::shared_ptr<Node>
    {
        all_nodes.emplace_back(std::make_shared<Node>());
        all_nodes.back()->unique_index = all_nodes.size() - 1;
        return all_nodes.back();
    }

    constexpr auto get_node_count() const
    {
        return all_nodes.size();
    }

    constexpr void delete_node(std::shared_ptr<Node> node)
    {
        auto index = std::exchange(node->unique_index, std::numeric_limits<std::size_t>::max());
        all_nodes[index] = nullptr;

        if (index != all_nodes.size() - 1)
        {
            std::swap(all_nodes[index], all_nodes.back());
            all_nodes[index]->unique_index = index;
        }

        all_nodes.pop_back();
    }

    constexpr void garbage_collect()
    {
        for (int i = 0; i < all_nodes.size(); ++i)
        {
            if (all_nodes[i].use_count() > 1)
                continue;

            delete_node(all_nodes[i]);
        }
    }

    constexpr void delete_all_nodes()
    {
        all_nodes.clear();
    }
};

constexpr auto foo()
{
    auto ptr = NodeManager().create_node();
    return 5;
}

int main()
{
    constexpr auto x = foo();
    return 0;
}

Here is the compilation error I am getting:

example.cpp
<source>(36): error C3615: constexpr function 'NodeManager::create_node' cannot result in a constant expression
<source>(36): note: failure was because type 'std::shared_ptr<Node>' is not a literal type
C:/data/msvc/14.39.33321-Pre/include\memory(1649): note: type 'std::shared_ptr<Node>' is not a literal type because it has a user-defined destructor
<source>(39): note: failure was caused by call of undefined function or one not declared 'constexpr'
<source>(39): note: see usage of 'std::shared_ptr<Node>::operator ->'
<source>(40): note: failure was caused by call of undefined function or one not declared 'constexpr'
<source>(40): note: see usage of 'std::shared_ptr<Node>::shared_ptr'
<source>(48): error C3615: constexpr function 'NodeManager::delete_node' cannot result in a constant expression
<source>(48): note: failure was because type 'std::shared_ptr<Node>' is not a literal type
C:/data/msvc/14.39.33321-Pre/include\memory(1649): note: type 'std::shared_ptr<Node>' is not a literal type because it has a user-defined destructor
<source>(51): note: failure was caused by call of undefined function or one not declared 'constexpr'
<source>(51): note: see usage of 'std::shared_ptr<Node>::operator ='
<source>(87): error C2131: expression did not evaluate to a constant
<source>(81): note: function violates 'constexpr' rules or has errors
<source>(81): note: see usage of 'NodeManager::create_node'
<source>(87): note: the call stack of the evaluation (the oldest call first) is
<source>(87): note: while evaluating function 'int foo(void)'
<source>(81): note: while evaluating function 'std::shared_ptr<Node> NodeManager::create_node(void)'
Compiler returned: 2

Godbolt Link: https://godbolt.org/z/YbsrferP6

Thanks!

Answer 1

The compiler error tells you what's wrong:

<source>(40): note: failure was caused by call of undefined function or one not declared 'constexpr'
<source>(40): note: see usage of 'std::shared_ptr<Node>::shared_ptr

shared_ptr is not constexpr (see cppreference for make_shared and shared_ptr). unique_ptr can be used constexpr, but only since c++23. I'm not sure if operator new is even constexpr usable in c++20, I think that requires c++23 as well? Edit: I just looked it up. It can be constexpr used in c++20, but restrictions apply that seem relevant to your usage: https://stackoverflow.com/a/62404855/1480324

Either way, even if you can switch to c++23, you would need to use a unique_ptr instead of shared_ptr.