fd4a68dfff
Unit + integration coverage for the session's work: incremental project graph/index, pcode encoder, unreachable/dead-branch, equiv/cross-TU, div-by-zero/sign-conversion/int-truncation, use-after-free, quality-precision, scan-router profile, source TU runner, detector plan, and the eval fixtures.
368 lines
16 KiB
C++
368 lines
16 KiB
C++
#include <algorithm>
|
|
#include <catch2/catch_test_macros.hpp>
|
|
#include <chrono>
|
|
#include <nlohmann/json.hpp>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
#include "fold/analysis/production_reachability.hpp"
|
|
#include "fold/cli/production_reachability_findings.hpp"
|
|
#include "fold/config/configuration_profile.hpp"
|
|
#include "fold/ir/call_graph.hpp"
|
|
#include "fold/ir/config_guard.hpp"
|
|
#include "fold/report/finding_json.hpp"
|
|
|
|
namespace {
|
|
|
|
using fold::analysis::ProductionReachabilityClass;
|
|
using fold::analysis::ProductionReachabilityRecord;
|
|
using fold::analysis::ProductionRootInventory;
|
|
using fold::analysis::ProductionRootKind;
|
|
using fold::analysis::ProductionRootRecord;
|
|
|
|
ProductionRootRecord root(std::string id, bool production = true, bool conditional = false) {
|
|
return {
|
|
.function_usr = id,
|
|
.qualified_name = id,
|
|
.source_file = production ? "/src/app.cpp" : "/tests/app_test.cpp",
|
|
.kind = production ? ProductionRootKind::Main : ProductionRootKind::TestEntry,
|
|
.evidence_file = production ? "/src/app.cpp" : "/tests/app_test.cpp",
|
|
.evidence_line = 1,
|
|
.evidence_column = 1,
|
|
.production = production,
|
|
.conditional = conditional,
|
|
};
|
|
}
|
|
|
|
void addFunction(fold::ir::ProjectCallGraph& graph, const std::string& id, bool escapes = false) {
|
|
graph.addFunction(id, id, "/src/app.cpp", true, "body-" + id, escapes);
|
|
}
|
|
|
|
const ProductionReachabilityRecord&
|
|
findRecord(const fold::analysis::ProductionReachabilityResult& result, const std::string& id) {
|
|
const auto found =
|
|
std::ranges::find(result.records, id, &ProductionReachabilityRecord::function_usr);
|
|
REQUIRE(found != result.records.end());
|
|
return *found;
|
|
}
|
|
|
|
fold::SolverBudget budget() {
|
|
fold::SolverBudget result;
|
|
result.per_query = std::chrono::milliseconds(100);
|
|
result.total = std::chrono::milliseconds(2000);
|
|
return result;
|
|
}
|
|
|
|
fold::index::GuardedCallsiteRecord guarded(const std::string& caller, const std::string& callee,
|
|
const fold::ir::ConfigGuard& guard,
|
|
std::string suffix = "1") {
|
|
return {
|
|
.callsite_id = caller + "-" + callee + "-" + suffix,
|
|
.caller_usr = caller,
|
|
.direct_target_usr = callee,
|
|
.edge_kind = fold::index::EdgeKind::Direct,
|
|
.guard = guard,
|
|
};
|
|
}
|
|
|
|
} // namespace
|
|
|
|
TEST_CASE("closed-world reachability separates production test and unreachable functions",
|
|
"[production-reachability]") {
|
|
fold::ir::ProjectCallGraph graph;
|
|
for (const auto* id : {"main", "live", "test_main", "test_helper", "dead"})
|
|
addFunction(graph, id);
|
|
graph.addCallEdge("main", "live");
|
|
graph.addCallEdge("test_main", "test_helper");
|
|
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
roots.test_roots.push_back(root("test_main", false));
|
|
const auto result =
|
|
fold::analysis::classifyProductionReachability(graph, roots, {}, nullptr, budget());
|
|
|
|
CHECK(findRecord(result, "main").classification ==
|
|
ProductionReachabilityClass::ProductionReachable);
|
|
const auto& live = findRecord(result, "live");
|
|
CHECK(live.classification == ProductionReachabilityClass::ProductionReachable);
|
|
CHECK(live.witness == std::vector<std::string>{"main", "live"});
|
|
CHECK(findRecord(result, "test_helper").classification ==
|
|
ProductionReachabilityClass::TestOnly);
|
|
const auto& dead = findRecord(result, "dead");
|
|
CHECK(dead.classification == ProductionReachabilityClass::UnreachableProduction);
|
|
CHECK(dead.removal_candidate);
|
|
CHECK(result.stats.removal_candidates == 1);
|
|
CHECK(result.stats.solver_queries == 0);
|
|
|
|
const auto findings = fold::cli::makeProductionReachabilityFindings(result);
|
|
const auto dead_finding = std::ranges::find_if(findings, [](const auto& finding) {
|
|
return finding.evidence.reachability &&
|
|
finding.evidence.reachability->classification == "unreachable-production";
|
|
});
|
|
REQUIRE(dead_finding != findings.end());
|
|
REQUIRE(dead_finding->evidence.reachability);
|
|
CHECK(dead_finding->evidence.reachability->removal_candidate);
|
|
CHECK(dead_finding->evidence.path_trace.empty());
|
|
REQUIRE(dead_finding->evidence.quality);
|
|
CHECK(dead_finding->evidence.quality->member_ids.empty());
|
|
const auto round_trip = fold::findingFromJson(fold::findingToJson(*dead_finding));
|
|
CHECK(round_trip.kind == fold::FindingKind::ProductionReachability);
|
|
REQUIRE(round_trip.evidence.reachability);
|
|
CHECK(round_trip.evidence.reachability->classification == "unreachable-production");
|
|
CHECK(round_trip.evidence.reachability->removal_candidate);
|
|
}
|
|
|
|
TEST_CASE("incomplete evidence and conditional roots cannot prove production unreachability",
|
|
"[production-reachability][fail-closed]") {
|
|
fold::ir::ProjectCallGraph graph;
|
|
addFunction(graph, "main");
|
|
addFunction(graph, "maybe");
|
|
addFunction(graph, "escaped", true);
|
|
addFunction(graph, "escape_child");
|
|
addFunction(graph, "virtual");
|
|
graph.addCallEdge("escaped", "escape_child");
|
|
graph.addCallEdge("virtual", "maybe");
|
|
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
roots.conditional_roots.push_back(root("virtual", true, true));
|
|
roots.closed_world = false;
|
|
roots.has_unresolved_dynamic_calls = true;
|
|
const auto result =
|
|
fold::analysis::classifyProductionReachability(graph, roots, {}, nullptr, budget());
|
|
CHECK(result.stats.solver_queries == 0);
|
|
|
|
for (const auto* id : {"maybe", "escaped", "escape_child", "virtual"}) {
|
|
const auto& record = findRecord(result, id);
|
|
CHECK(record.classification == ProductionReachabilityClass::ProductionReachable);
|
|
CHECK_FALSE(record.complete);
|
|
CHECK_FALSE(record.removal_candidate);
|
|
CHECK(std::ranges::find(record.blockers, "unresolved-dynamic-call") !=
|
|
record.blockers.end());
|
|
}
|
|
}
|
|
|
|
TEST_CASE("guards distinguish default-inactive and configuration-infeasible paths",
|
|
"[production-reachability][guards]") {
|
|
const auto parsed = fold::config::parseConfigurationProfile(nlohmann::json{
|
|
{"version", 1},
|
|
{"entrypoints", {"main"}},
|
|
{"assumptions", {{{"kind", "global"}, {"selector", "feature"}, {"value", false}}}},
|
|
});
|
|
REQUIRE(parsed.ok());
|
|
const auto& profile = *parsed.profile;
|
|
const std::string symbol = profile.assumptions().front().symbolId().value();
|
|
|
|
fold::ir::ProjectCallGraph graph;
|
|
for (const auto* id : {"main", "feature", "impossible"})
|
|
addFunction(graph, id);
|
|
graph.addCallEdge("main", "feature");
|
|
graph.addCallEdge("main", "impossible");
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
const std::vector calls = {
|
|
guarded("main", "feature",
|
|
fold::ir::ConfigGuard::projected(fold::ir::ConfigGuardExpr::boolSymbol(symbol))),
|
|
guarded("main", "impossible",
|
|
fold::ir::ConfigGuard::projected(fold::ir::ConfigGuardExpr::boolean(false))),
|
|
};
|
|
|
|
const auto result =
|
|
fold::analysis::classifyProductionReachability(graph, roots, calls, &profile, budget());
|
|
const auto& feature = findRecord(result, "feature");
|
|
CHECK(feature.classification == ProductionReachabilityClass::DefaultInactive);
|
|
CHECK(feature.default_result == fold::analysis::ReachabilityProofResult::Unsat);
|
|
CHECK(feature.free_configuration_result == fold::analysis::ReachabilityProofResult::Sat);
|
|
CHECK_FALSE(feature.removal_candidate);
|
|
const auto& impossible = findRecord(result, "impossible");
|
|
CHECK(impossible.classification == ProductionReachabilityClass::ConfigurationInfeasible);
|
|
CHECK(impossible.free_configuration_result == fold::analysis::ReachabilityProofResult::Unsat);
|
|
CHECK_FALSE(impossible.removal_candidate);
|
|
}
|
|
|
|
TEST_CASE("guard constraints remain correlated across a path",
|
|
"[production-reachability][guards]") {
|
|
const auto parsed = fold::config::parseConfigurationProfile(nlohmann::json{
|
|
{"version", 1},
|
|
{"entrypoints", {"main"}},
|
|
{"assumptions", {{{"kind", "global"}, {"selector", "feature"}, {"value", true}}}},
|
|
});
|
|
REQUIRE(parsed.ok());
|
|
const auto& profile = *parsed.profile;
|
|
const auto enabled =
|
|
fold::ir::ConfigGuardExpr::boolSymbol(profile.assumptions().front().symbolId().value());
|
|
const auto disabled = fold::ir::ConfigGuardExpr::apply(fold::ir::ConfigGuardOp::Not, {enabled});
|
|
|
|
fold::ir::ProjectCallGraph graph;
|
|
for (const auto* id : {"main", "middle", "target"})
|
|
addFunction(graph, id);
|
|
graph.addCallEdge("main", "middle");
|
|
graph.addCallEdge("middle", "target");
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
const std::vector calls = {
|
|
guarded("main", "middle", fold::ir::ConfigGuard::projected(enabled)),
|
|
guarded("middle", "target", fold::ir::ConfigGuard::projected(disabled)),
|
|
};
|
|
|
|
const auto result =
|
|
fold::analysis::classifyProductionReachability(graph, roots, calls, &profile, budget());
|
|
const auto& target = findRecord(result, "target");
|
|
CHECK(target.classification == ProductionReachabilityClass::ConfigurationInfeasible);
|
|
CHECK(target.free_configuration_result == fold::analysis::ReachabilityProofResult::Unsat);
|
|
CHECK_FALSE(target.removal_candidate);
|
|
CHECK(result.stats.solver_queries == 3);
|
|
}
|
|
|
|
TEST_CASE("equivalent guarded reachability is reused through unconditional chains",
|
|
"[production-reachability][guards][reuse]") {
|
|
const auto parsed = fold::config::parseConfigurationProfile(nlohmann::json{
|
|
{"version", 1},
|
|
{"entrypoints", {"main"}},
|
|
{"assumptions", {{{"kind", "global"}, {"selector", "feature"}, {"value", false}}}},
|
|
});
|
|
REQUIRE(parsed.ok());
|
|
const auto& profile = *parsed.profile;
|
|
const auto enabled =
|
|
fold::ir::ConfigGuardExpr::boolSymbol(profile.assumptions().front().symbolId().value());
|
|
|
|
fold::ir::ProjectCallGraph graph;
|
|
for (const auto* id : {"main", "gated", "middle", "target"})
|
|
addFunction(graph, id);
|
|
graph.addCallEdge("main", "gated");
|
|
graph.addCallEdge("gated", "middle");
|
|
graph.addCallEdge("middle", "target");
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
const std::vector calls = {
|
|
guarded("main", "gated", fold::ir::ConfigGuard::projected(enabled)),
|
|
guarded("gated", "middle", fold::ir::ConfigGuard::unconditional()),
|
|
guarded("middle", "target", fold::ir::ConfigGuard::unconditional()),
|
|
};
|
|
|
|
const auto result =
|
|
fold::analysis::classifyProductionReachability(graph, roots, calls, &profile, budget());
|
|
CHECK(result.stats.solver_queries == 2);
|
|
for (const auto* id : {"gated", "middle", "target"}) {
|
|
CHECK(findRecord(result, id).classification ==
|
|
ProductionReachabilityClass::DefaultInactive);
|
|
}
|
|
CHECK(findRecord(result, "target").witness ==
|
|
std::vector<std::string>{"main", "gated", "middle", "target"});
|
|
const auto findings = fold::cli::makeProductionReachabilityFindings(result);
|
|
const auto target_finding = std::ranges::find_if(findings, [](const auto& finding) {
|
|
return finding.evidence.reachability &&
|
|
finding.evidence.reachability->witness ==
|
|
std::vector<std::string>{"main", "gated", "middle", "target"};
|
|
});
|
|
REQUIRE(target_finding != findings.end());
|
|
CHECK(target_finding->evidence.path_trace.empty());
|
|
REQUIRE(target_finding->evidence.quality);
|
|
CHECK(target_finding->evidence.quality->member_ids.empty());
|
|
const auto wire = fold::findingToJson(*target_finding);
|
|
CHECK(wire["evidence"]["path_trace"] ==
|
|
nlohmann::json::array({"main", "gated", "middle", "target"}));
|
|
CHECK(wire["evidence"]["quality"]["member_ids"] ==
|
|
nlohmann::json::array({"main", "gated", "middle", "target"}));
|
|
|
|
const auto limited = fold::analysis::classifyProductionReachability(
|
|
graph, roots, calls, &profile, budget(), {.max_witness_functions = 2});
|
|
CHECK(findRecord(limited, "target").witness == std::vector<std::string>{"middle", "target"});
|
|
CHECK(limited.stats.truncated_witnesses == 2);
|
|
}
|
|
|
|
TEST_CASE("multiple guarded callsites are alternatives rather than a conjunction",
|
|
"[production-reachability][guards]") {
|
|
const auto parsed = fold::config::parseConfigurationProfile(nlohmann::json{
|
|
{"version", 1},
|
|
{"entrypoints", {"main"}},
|
|
{"assumptions", {{{"kind", "global"}, {"selector", "feature"}, {"value", false}}}},
|
|
});
|
|
REQUIRE(parsed.ok());
|
|
const auto& profile = *parsed.profile;
|
|
const auto symbol = profile.assumptions().front().symbolId().value();
|
|
const auto enabled = fold::ir::ConfigGuardExpr::boolSymbol(symbol);
|
|
const auto disabled = fold::ir::ConfigGuardExpr::apply(fold::ir::ConfigGuardOp::Not, {enabled});
|
|
|
|
fold::ir::ProjectCallGraph graph;
|
|
addFunction(graph, "main");
|
|
addFunction(graph, "target");
|
|
graph.addCallEdge("main", "target");
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
const std::vector calls = {
|
|
guarded("main", "target", fold::ir::ConfigGuard::projected(enabled), "enabled"),
|
|
guarded("main", "target", fold::ir::ConfigGuard::projected(disabled), "disabled"),
|
|
};
|
|
|
|
const auto result =
|
|
fold::analysis::classifyProductionReachability(graph, roots, calls, &profile, budget());
|
|
CHECK(findRecord(result, "target").classification ==
|
|
ProductionReachabilityClass::ProductionReachable);
|
|
auto reversed_calls = calls;
|
|
std::ranges::reverse(reversed_calls);
|
|
const auto reversed = fold::analysis::classifyProductionReachability(
|
|
graph, roots, reversed_calls, &profile, budget());
|
|
CHECK(findRecord(reversed, "target").classification ==
|
|
findRecord(result, "target").classification);
|
|
CHECK(findRecord(reversed, "target").witness == findRecord(result, "target").witness);
|
|
}
|
|
|
|
TEST_CASE("recursive SCCs require a rooted incoming path", "[production-reachability][scc]") {
|
|
fold::ir::ProjectCallGraph graph;
|
|
for (const auto* id : {"main", "a", "b"})
|
|
addFunction(graph, id);
|
|
graph.addCallEdge("a", "b");
|
|
graph.addCallEdge("b", "a");
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
|
|
const auto disconnected =
|
|
fold::analysis::classifyProductionReachability(graph, roots, {}, nullptr, budget());
|
|
CHECK(findRecord(disconnected, "a").classification ==
|
|
ProductionReachabilityClass::UnreachableProduction);
|
|
CHECK(findRecord(disconnected, "b").removal_candidate);
|
|
|
|
graph.addCallEdge("main", "a");
|
|
const auto connected =
|
|
fold::analysis::classifyProductionReachability(graph, roots, {}, nullptr, budget());
|
|
CHECK(findRecord(connected, "a").classification ==
|
|
ProductionReachabilityClass::ProductionReachable);
|
|
CHECK(findRecord(connected, "b").classification ==
|
|
ProductionReachabilityClass::ProductionReachable);
|
|
}
|
|
|
|
TEST_CASE("limits and unknown guards fail closed", "[production-reachability][fail-closed]") {
|
|
fold::ir::ProjectCallGraph graph;
|
|
addFunction(graph, "main");
|
|
addFunction(graph, "target");
|
|
graph.addCallEdge("main", "target");
|
|
ProductionRootInventory roots;
|
|
roots.production_roots.push_back(root("main"));
|
|
|
|
auto limited = fold::analysis::classifyProductionReachability(graph, roots, {}, nullptr,
|
|
budget(), {.max_functions = 1});
|
|
CHECK_FALSE(limited.complete);
|
|
CHECK_FALSE(findRecord(limited, "target").removal_candidate);
|
|
|
|
const std::vector calls = {
|
|
guarded("main", "target", fold::ir::ConfigGuard::unknown()),
|
|
};
|
|
const auto unknown =
|
|
fold::analysis::classifyProductionReachability(graph, roots, calls, nullptr, budget());
|
|
const auto& target = findRecord(unknown, "target");
|
|
CHECK(target.classification == ProductionReachabilityClass::ProductionReachable);
|
|
CHECK_FALSE(target.complete);
|
|
CHECK_FALSE(target.removal_candidate);
|
|
CHECK(std::ranges::find(target.blockers, "unknown-guard") != target.blockers.end());
|
|
|
|
auto exhausted_budget = budget();
|
|
exhausted_budget.total = std::chrono::milliseconds(0);
|
|
const auto exhausted = fold::analysis::classifyProductionReachability(
|
|
graph, roots, calls, nullptr, exhausted_budget);
|
|
const auto& exhausted_target = findRecord(exhausted, "target");
|
|
CHECK(exhausted_target.classification == ProductionReachabilityClass::ProductionReachable);
|
|
CHECK_FALSE(exhausted_target.complete);
|
|
CHECK_FALSE(exhausted_target.removal_candidate);
|
|
CHECK(exhausted.stats.solver_timeouts > 0);
|
|
}
|