18665697691

Committed 20 Oct 2025 09:40PM UTC coverage: 96.115% (+0.8%) from 95.331%

Build # 18665697691

Build Type

Pull #173

github

Committed by

web-flow

Commit Message

Merge 2256c96a7 into b6741487e

Pull Request Pull Request #173: Add support for correctly handling BTF data with cycles

Run Details

883 of 925 new or added lines in 6 files covered. (95.46%)

1 existing line in 1 file now uncovered.

2177 of 2265 relevant lines covered (96.11%)

1581.57 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.33

/test/test_cycle_detector.cpp

// Copyright (c) Prevail Verifier contributors.
// SPDX-License-Identifier: MIT

#include "cycle_detector.h"
#include <catch2/catch_test_macros.hpp>
#include <stdexcept>

using namespace libbtf;

TEST_CASE("cycle_detector basic functionality", "[cycle_detector]") {
  cycle_detector detector;

  SECTION("Initial state") {
    REQUIRE_FALSE(detector.would_create_cycle(1));
    REQUIRE(detector.get_visited().empty());
  }

  SECTION("Mark and check visited") {
    REQUIRE(detector.mark_visited(1));
    REQUIRE(detector.would_create_cycle(1));
    REQUIRE(detector.get_visited().size() == 1);
    REQUIRE(detector.get_visited().count(1) == 1);

    // Trying to mark the same ID again should return false
    REQUIRE_FALSE(detector.mark_visited(1));
  }

  SECTION("Unmark visited") {
    detector.mark_visited(1);
    detector.mark_visited(2);
    REQUIRE(detector.get_visited().size() == 2);

    detector.unmark_visited(1);
    REQUIRE_FALSE(detector.would_create_cycle(1));
    REQUIRE(detector.would_create_cycle(2));
    REQUIRE(detector.get_visited().size() == 1);
  }

  SECTION("Clear all") {
    detector.mark_visited(1);
    detector.mark_visited(2);
    detector.mark_visited(3);

    detector.clear();
    REQUIRE(detector.get_visited().empty());
    REQUIRE_FALSE(detector.would_create_cycle(1));
    REQUIRE_FALSE(detector.would_create_cycle(2));
    REQUIRE_FALSE(detector.would_create_cycle(3));
  }
}

TEST_CASE("cycle_detector with_cycle_detection method", "[cycle_detector]") {
  cycle_detector detector;

  SECTION("No cycle - calls main function") {
    int result = detector.with_cycle_detection<int>(
        1, []() { return 42; }, []() { return -1; });
    REQUIRE(result == 42);
  }

  SECTION("Cycle detected - calls cycle handler") {
    detector.mark_visited(1); // Pre-mark to simulate cycle

    int result = detector.with_cycle_detection<int>(
        1, []() { return 42; }, []() { return -1; });
    REQUIRE(result == -1);
  }

  SECTION("Backtracking enabled by default") {
    detector.with_cycle_detection<int>(
        1, []() { return 42; }, []() { return -1; });

    // After the call, ID should be unmarked due to backtracking
    REQUIRE_FALSE(detector.would_create_cycle(1));
  }

  SECTION("Backtracking disabled") {
    detector.with_cycle_detection<int>(
        1, []() { return 42; }, []() { return -1; },
        false // backtrack = false
    );

    // After the call, ID should still be marked
    REQUIRE(detector.would_create_cycle(1));
  }
}

TEST_CASE("scoped_visit RAII behavior", "[cycle_detector][scoped_visit]") {
  cycle_detector detector;

  SECTION("Successful visit and automatic cleanup") {
    {
      scoped_visit visit(detector, 1, std::nothrow);
      REQUIRE(visit.is_marked());
      REQUIRE(detector.would_create_cycle(1));
    }
    // After scope, should be automatically unmarked
    REQUIRE_FALSE(detector.would_create_cycle(1));
  }

  SECTION("Cycle detected - no marking") {
    detector.mark_visited(1); // Pre-mark

    {
      scoped_visit visit(detector, 1, std::nothrow);
      REQUIRE_FALSE(visit.is_marked()); // Should detect cycle
    }

    // Should still be marked from the original mark_visited call
    REQUIRE(detector.would_create_cycle(1));
  }

  SECTION("Exception throwing constructor") {
    detector.mark_visited(1); // Pre-mark to cause cycle

    REQUIRE_THROWS_AS(scoped_visit(detector, 1), std::runtime_error);
  }

  SECTION("Multiple scoped visits") {
    {
      scoped_visit visit1(detector, 1, std::nothrow);
      REQUIRE(visit1.is_marked());

      {
        scoped_visit visit2(detector, 2, std::nothrow);
        REQUIRE(visit2.is_marked());
        REQUIRE(detector.get_visited().size() == 2);
      }

      // visit2 should be cleaned up, visit1 still active
      REQUIRE(detector.get_visited().size() == 1);
      REQUIRE(detector.would_create_cycle(1));
      REQUIRE_FALSE(detector.would_create_cycle(2));
    }

    // All should be cleaned up
    REQUIRE(detector.get_visited().empty());
  }
}

TEST_CASE("Real-world usage patterns", "[cycle_detector][integration]") {
  cycle_detector detector;

  SECTION("Simulated recursive type size calculation") {
    // Simulate calculating size of recursive types
    std::function<int(int, cycle_detector &)> calc_size =
        [&](int type_id, cycle_detector &det) -> int {
      return det.with_cycle_detection<int>(
          type_id,
          [&]() -> int {
            // Simulate different type sizes
            if (type_id == 1)
              return 4; // int
            if (type_id == 2)
              return 8; // double
            if (type_id == 3)
              return calc_size(1, det) + calc_size(2, det); // struct
            if (type_id == 4)
              return calc_size(4, det); // self-referential (cycle)
            return 0;
          },
          [&]() -> int {
            return 0; // Cycle detected, return 0
          });
    };

    REQUIRE(calc_size(1, detector) == 4);
    REQUIRE(calc_size(2, detector) == 8);
    REQUIRE(calc_size(3, detector) == 12); // 4 + 8
    REQUIRE(calc_size(4, detector) == 0);  // Cycle detected
  }

  SECTION("Simulated type name resolution with cycles") {
    std::map<int, std::string> type_names = {
        {1, "int"}, {2, "MyStruct"}, {3, "ptr_to_2"}};

    std::map<int, int> type_refs = {
        {3, 2}, // ptr_to_2 -> MyStruct
        {2, 3}  // MyStruct -> ptr_to_2 (creates cycle)
    };

    std::function<std::string(int, cycle_detector &)> get_name =
        [&](int type_id, cycle_detector &det) -> std::string {
      scoped_visit visit(det, type_id, std::nothrow);
      if (!visit.is_marked()) {
        return "cyclic_type_" + std::to_string(type_id);
      }

      // Check for references first to ensure cycles are encountered
      auto ref_it = type_refs.find(type_id);
      if (ref_it != type_refs.end()) {
        return "ref_to_" + get_name(ref_it->second, det);
      }

      auto name_it = type_names.find(type_id);
      if (name_it != type_names.end()) {
        return name_it->second;
      }

      return "unknown_" + std::to_string(type_id);
    };

    REQUIRE(get_name(1, detector) == "int");
    // Type 2 and 3 have a cycle, should be detected
    std::string result2 = get_name(2, detector);
    std::string result3 = get_name(3, detector);

    // One of them should detect the cycle
    REQUIRE((result2.find("cyclic_type") != std::string::npos ||
             result3.find("cyclic_type") != std::string::npos));
  }
}

TEST_CASE("Performance considerations", "[cycle_detector][performance]") {
  cycle_detector detector;

  SECTION("Large number of types") {
    const int num_types = 10000;

    // Mark many types as visited
    for (int i = 0; i < num_types; ++i) {
      REQUIRE(detector.mark_visited(i));
    }

    REQUIRE(detector.get_visited().size() == num_types);

    // Check that lookups are still reasonably fast
    for (int i = 0; i < num_types; ++i) {
      REQUIRE(detector.would_create_cycle(i));
    }

    // Unmark all
    for (int i = 0; i < num_types; ++i) {
      detector.unmark_visited(i);
    }

    REQUIRE(detector.get_visited().empty());
  }
}

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3
4	#include "cycle_detector.h"
5	#include <catch2/catch_test_macros.hpp>
6	#include <stdexcept>
7
8	using namespace libbtf;
9
10	TEST_CASE("cycle_detector basic functionality", "[cycle_detector]") {	8✔
11	cycle_detector detector;	4✔
12
13	SECTION("Initial state") {	16✔
14	REQUIRE_FALSE(detector.would_create_cycle(1));	3✔
15	REQUIRE(detector.get_visited().empty());	2✔
16	}	8✔
17
18	SECTION("Mark and check visited") {	16✔
19	REQUIRE(detector.mark_visited(1));	2✔
20	REQUIRE(detector.would_create_cycle(1));	3✔
21	REQUIRE(detector.get_visited().size() == 1);	4✔
22	REQUIRE(detector.get_visited().count(1) == 1);	4✔
23
24	// Trying to mark the same ID again should return false
25	REQUIRE_FALSE(detector.mark_visited(1));	2✔
26	}	8✔
27
28	SECTION("Unmark visited") {	16✔
29	detector.mark_visited(1);	2✔
30	detector.mark_visited(2);	2✔
31	REQUIRE(detector.get_visited().size() == 2);	3✔
32
33	detector.unmark_visited(1);	2✔
34	REQUIRE_FALSE(detector.would_create_cycle(1));	3✔
35	REQUIRE(detector.would_create_cycle(2));	3✔
36	REQUIRE(detector.get_visited().size() == 1);	3✔
37	}	8✔
38
39	SECTION("Clear all") {	16✔
40	detector.mark_visited(1);	2✔
41	detector.mark_visited(2);	2✔
42	detector.mark_visited(3);	2✔
43
44	detector.clear();	1✔
45	REQUIRE(detector.get_visited().empty());	2✔
46	REQUIRE_FALSE(detector.would_create_cycle(1));	3✔
47	REQUIRE_FALSE(detector.would_create_cycle(2));	3✔
48	REQUIRE_FALSE(detector.would_create_cycle(3));	3✔
49	}	8✔
50	}	8✔
51
52	TEST_CASE("cycle_detector with_cycle_detection method", "[cycle_detector]") {	8✔
53	cycle_detector detector;	4✔
54
55	SECTION("No cycle - calls main function") {	16✔
56	int result = detector.with_cycle_detection<int>(	3✔
57	1, []() { return 42; }, []() { return -1; });	1✔
58	REQUIRE(result == 42);	3✔
59	}	8✔
60
61	SECTION("Cycle detected - calls cycle handler") {	16✔
62	detector.mark_visited(1); // Pre-mark to simulate cycle	2✔
63
64	int result = detector.with_cycle_detection<int>(	3✔
65	1, []() { return 42; }, []() { return -1; });	1✔
66	REQUIRE(result == -1);	3✔
67	}	8✔
68
69	SECTION("Backtracking enabled by default") {	16✔
70	detector.with_cycle_detection<int>(	3✔
71	1, []() { return 42; }, []() { return -1; });	1✔
72
73	// After the call, ID should be unmarked due to backtracking
74	REQUIRE_FALSE(detector.would_create_cycle(1));	3✔
75	}	8✔
76
77	SECTION("Backtracking disabled") {	16✔
78	detector.with_cycle_detection<int>(	3✔
79	1, []() { return 42; }, []() { return -1; },	1✔
80	false // backtrack = false
81	);
82
83	// After the call, ID should still be marked
84	REQUIRE(detector.would_create_cycle(1));	3✔
85	}	8✔
86	}	8✔
87
88	TEST_CASE("scoped_visit RAII behavior", "[cycle_detector][scoped_visit]") {	8✔
89	cycle_detector detector;	4✔
90
91	SECTION("Successful visit and automatic cleanup") {	16✔
92	{
93	scoped_visit visit(detector, 1, std::nothrow);	1✔
94	REQUIRE(visit.is_marked());	2✔
95	REQUIRE(detector.would_create_cycle(1));	3✔
96	}	1✔
97	// After scope, should be automatically unmarked
98	REQUIRE_FALSE(detector.would_create_cycle(1));	3✔
99	}	8✔
100
101	SECTION("Cycle detected - no marking") {	16✔
102	detector.mark_visited(1); // Pre-mark	2✔
103
104	{
105	scoped_visit visit(detector, 1, std::nothrow);	1✔
106	REQUIRE_FALSE(visit.is_marked()); // Should detect cycle	2✔
107	}	1✔
108
109	// Should still be marked from the original mark_visited call
110	REQUIRE(detector.would_create_cycle(1));	3✔
111	}	8✔
112
113	SECTION("Exception throwing constructor") {	16✔
114	detector.mark_visited(1); // Pre-mark to cause cycle	2✔
115
116	REQUIRE_THROWS_AS(scoped_visit(detector, 1), std::runtime_error);	2✔
117	}	8✔
118
119	SECTION("Multiple scoped visits") {	16✔
120	{
121	scoped_visit visit1(detector, 1, std::nothrow);	1✔
122	REQUIRE(visit1.is_marked());	2✔
123
124	{
125	scoped_visit visit2(detector, 2, std::nothrow);	1✔
126	REQUIRE(visit2.is_marked());	2✔
127	REQUIRE(detector.get_visited().size() == 2);	3✔
128	}	1✔
129
130	// visit2 should be cleaned up, visit1 still active
131	REQUIRE(detector.get_visited().size() == 1);	3✔
132	REQUIRE(detector.would_create_cycle(1));	3✔
133	REQUIRE_FALSE(detector.would_create_cycle(2));	3✔
134	}	1✔
135
136	// All should be cleaned up
137	REQUIRE(detector.get_visited().empty());	2✔
138	}	8✔
139	}	8✔
140
141	TEST_CASE("Real-world usage patterns", "[cycle_detector][integration]") {	4✔
142	cycle_detector detector;	2✔
143
144	SECTION("Simulated recursive type size calculation") {	8✔
145	// Simulate calculating size of recursive types
146	std::function<int(int, cycle_detector &)> calc_size =
147	[&](int type_id, cycle_detector &det) -> int {	14✔
148	return det.with_cycle_detection<int>(	35✔
149	type_id,
150	[&]() -> int {	12✔
151	// Simulate different type sizes
152	if (type_id == 1)	12✔
153	return 4; // int	2✔
154	if (type_id == 2)	8✔
155	return 8; // double	2✔
156	if (type_id == 3)	4✔
157	return calc_size(1, det) + calc_size(2, det); // struct	19✔
158	if (type_id == 4)	2✔
159	return calc_size(4, det); // self-referential (cycle)	2✔
160	return 0;
161	},
162	[&]() -> int {	1✔
163	return 0; // Cycle detected, return 0	1✔
164	});	21✔
165	};	1✔
166
167	REQUIRE(calc_size(1, detector) == 4);	4✔
168	REQUIRE(calc_size(2, detector) == 8);	4✔
169	REQUIRE(calc_size(3, detector) == 12); // 4 + 8	4✔
170	REQUIRE(calc_size(4, detector) == 0); // Cycle detected	4✔
171	}	5✔
172
173	SECTION("Simulated type name resolution with cycles") {	8✔
174	std::map<int, std::string> type_names = {
175	{1, "int"}, {2, "MyStruct"}, {3, "ptr_to_2"}};	9✔
176
177	std::map<int, int> type_refs = {
178	{3, 2}, // ptr_to_2 -> MyStruct
179	{2, 3} // MyStruct -> ptr_to_2 (creates cycle)
180	};	2✔
181
182	std::function<std::string(int, cycle_detector &)> get_name =
183	[&](int type_id, cycle_detector &det) -> std::string {	14✔
184	scoped_visit visit(det, type_id, std::nothrow);	14✔
185	if (!visit.is_marked()) {	14✔
186	return "cyclic_type_" + std::to_string(type_id);	8✔
187	}
188
189	// Check for references first to ensure cycles are encountered
190	auto ref_it = type_refs.find(type_id);	10✔
191	if (ref_it != type_refs.end()) {	10✔
192	return "ref_to_" + get_name(ref_it->second, det);	20✔
193	}
194
195	auto name_it = type_names.find(type_id);	2✔
196	if (name_it != type_names.end()) {	2✔
197	return name_it->second;	1✔
198	}
199
NEW 200	return "unknown_" + std::to_string(type_id);	×
201	};	9✔
202
203	REQUIRE(get_name(1, detector) == "int");	4✔
204	// Type 2 and 3 have a cycle, should be detected
205	std::string result2 = get_name(2, detector);	2✔
206	std::string result3 = get_name(3, detector);	2✔
207
208	// One of them should detect the cycle
209	REQUIRE((result2.find("cyclic_type") != std::string::npos \|\|	2✔
210	result3.find("cyclic_type") != std::string::npos));
211	}	5✔
212	}	4✔
213
214	TEST_CASE("Performance considerations", "[cycle_detector][performance]") {	2✔
215	cycle_detector detector;	1✔
216
217	SECTION("Large number of types") {	4✔
218	const int num_types = 10000;	1✔
219
220	// Mark many types as visited
221	for (int i = 0; i < num_types; ++i) {	20,002✔
222	REQUIRE(detector.mark_visited(i));	20,000✔
223	}
224
225	REQUIRE(detector.get_visited().size() == num_types);	3✔
226
227	// Check that lookups are still reasonably fast
228	for (int i = 0; i < num_types; ++i) {	20,002✔
229	REQUIRE(detector.would_create_cycle(i));	30,000✔
230	}
231
232	// Unmark all
233	for (int i = 0; i < num_types; ++i) {	20,002✔
234	detector.unmark_visited(i);	20,000✔
235	}
236
237	REQUIRE(detector.get_visited().empty());	2✔
238	}	2✔
239	}	2✔

Alan-Jowett / libbtf / 18665697691

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous