28060332906

Committed 31 Mar 2026 06:26PM UTC coverage: 92.773% (-2.3%) from 95.029%

Build # 28060332906

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #194 from Alan-Jowett/dependabot/github_actions/actions-f78bc712d6

Bump the actions group with 3 updates

Coverage Stats

2285 of 2463 relevant lines covered (92.77%)

768.8 hits per line

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

98.68

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

Alan-Jowett / libbtf / 28060332906

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