I have this code below that recursively traverses the nodes of a graph (for simplicity, only the edges are shown here). I would expect the result of the count_dfs()
function to be 4
regardless of whether the function is evaluated at runtime or compile time.
On MVSC this isn't the case. It works as expected on Clang and gcc, so I'd assume this is a bug in MSVC. Or is there some UB in the code? A far as I know, UB isn't allowed in constant expressions, right? Are there any circumstances under which a function can yield different results in constexpr and non-constexpr execution?
#include <iostream>
#include <ranges>
#include <array>
struct Edge
{
int from{};
int to{};
};
constexpr auto node_input_edges(auto& edges, int id)
{
return edges | std::views::filter([id](const Edge& e) { return e.to == id; });
}
constexpr void visit_dfs(auto& edges, int curr_node, auto func)
{
for (auto e : node_input_edges(edges, curr_node)) {
visit_dfs(edges, e.from, func);
}
func();
}
constexpr auto count_dfs()
{
std::array<Edge, 3> edges{{{0,2}, {1,2}, {2,3}}};
size_t sz = 0;
visit_dfs(edges, int(edges.size()), [&]() {
sz;
});
return sz;
}
int main()
{
constexpr auto cnt_ct = count_dfs();
auto cnt_rt = count_dfs();
std::cout << "COMPILE TIME " << cnt_ct << "\n"; // 3 on MSVC, 4 on clang and gcc
std::cout << "RUNTIME " << cnt_rt << "\n"; // 4 on all compilers
return 0;
}
CodePudding user response:
It looks like an issue with how MSVC treats views. Here is a somewhat ugly but equivalent code that works without views:
#include <iostream>
#include <ranges>
#include <array>
struct Edge
{
int from{};
int to{};
};
template<std::size_t n>
constexpr auto node_input_edges(std::array<Edge, n> const& edges, int id)
{
std::array<Edge, n> edges_copy;
auto j = 0;
for (auto i = 0; i < n; i) {
if (edges[i].to == id) {
edges_copy[j] = edges[i];
j;
}
}
if (j != n) {
edges_copy[j] = {0, 0}; // similar to a null terminator
}
return edges_copy;
}
constexpr void visit_dfs(auto const& edges, int curr_node, auto func)
{
for (auto const& e : node_input_edges(edges, curr_node)) {
if (e.from == 0 && e.to == 0) { // check for the null terminator
break;
}
visit_dfs(edges, e.from, func);
}
func();
}
constexpr auto count_dfs()
{
std::array<Edge, 3> edges{{{0,2}, {1,2}, {2,3}}};
size_t sz = 0;
visit_dfs(edges, 3, [&]() {
sz;
});
return sz;
}
int main()
{
constexpr auto cnt_ct = count_dfs();
auto cnt_rt = count_dfs();
std::cout << "COMPILE TIME " << cnt_ct << "\n";
std::cout << "RUNTIME " << cnt_rt << "\n";
return 0;
}