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

88.7

/libbtf/btf_type_data.cpp

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

#include "btf_type_data.h"

#include "btf.h"
#include "btf_json.h"
#include "btf_parse.h"
#include "btf_write.h"
#include "cycle_detector.h"

#include <algorithm>
#include <iomanip>
#include <sstream>
#include <stdexcept>

namespace libbtf {

btf_type_data::btf_type_data(const std::vector<std::byte> &btf_data) {
  auto visitor = [&, this](btf_type_id id,
                           const std::optional<std::string> &name,
                           const btf_kind &kind) {
    this->id_to_kind.insert({id, kind});
    if (name.has_value()) {
      this->name_to_id.insert({name.value(), id});
    }
  };
  btf_parse_types(btf_data, visitor);
}

btf_type_id btf_type_data::get_id(const std::string &name) const {
  auto it = name_to_id.find(name);
  if (it == name_to_id.end()) {
    return 0;
  }
  return it->second;
}

btf_kind btf_type_data::get_kind(btf_type_id id) const {
  auto it = id_to_kind.find(id);
  if (it == id_to_kind.end()) {
    throw std::runtime_error("BTF type id not found: " + std::to_string(id));
  }
  return it->second;
}

btf_type_id btf_type_data::dereference_pointer(btf_type_id id) const {
  return get_kind_type<btf_kind_ptr>(id).type;
}

uint32_t btf_type_data::get_size(btf_type_id id) const {
  cycle_detector detector;
  return get_size_with_detector(id, detector);
}

uint32_t btf_type_data::get_size_with_detector(btf_type_id id,
                                               cycle_detector &detector) const {
  return detector.with_cycle_detection<uint32_t>(
      id,
      [this, id, &detector]() -> uint32_t {
        // Main processing logic - same as original but using detector
        return std::visit(
            [this, id, &detector](auto kind) -> uint32_t {
              if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
                return sizeof(void *);
              } else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
                return get_size_with_detector(kind.type, detector);
              } else if constexpr (btf_kind_traits<
                                       decltype(kind)>::has_size_in_bytes) {
                return kind.size_in_bytes;
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_array>) {
                return kind.count_of_elements *
                       get_size_with_detector(kind.element_type, detector);
              } else {
                return 0;
              }
            },
            get_kind(id));
      },
      []() -> uint32_t {
        // Cycle detected - return 0 to avoid infinite recursion
        return 0;
      });
}

void btf_type_data::to_json(
    std::ostream &out,
    std::optional<std::function<bool(btf_type_id)>> filter) const {
  btf_type_to_json(id_to_kind, out, filter);
}

std::vector<std::byte> btf_type_data::to_bytes() const {
  std::vector<btf_kind> kinds;
  for (const auto &[id, kind] : id_to_kind) {
    kinds.push_back(kind);
  }
  return btf_write_types(kinds);
}

void btf_type_data::replace(btf_type_id id, const btf_kind &kind) {
  if (id_to_kind.find(id) == id_to_kind.end()) {
    throw std::runtime_error("BTF type not found: " + std::to_string(id));
  }

  id_to_kind[id] = kind;
  update_name_to_id(id);
}

btf_type_id btf_type_data::append(const btf_kind &kind) {
  if (id_to_kind.size() > UINT32_MAX) {
    throw std::runtime_error("Too many BTF types");
  }
  btf_type_id next_id = static_cast<btf_type_id>(id_to_kind.size());
  id_to_kind.insert({next_id, kind});
  update_name_to_id(next_id);
  return next_id;
}

void btf_type_data::update_name_to_id(btf_type_id id) {

  auto name = get_type_name(id);
  if (!name.empty()) {
    name_to_id.insert({name, id});
  }
}

std::vector<btf_type_id> btf_type_data::dependency_order(
    std::optional<std::function<bool(btf_type_id)>> filter) const {
  std::map<btf_type_id, std::set<btf_type_id>> children;
  std::map<btf_type_id, std::set<btf_type_id>> parents;
  std::set<btf_type_id> filtered_types;
  std::vector<btf_type_id> result;

  // Build list of dependencies manually to avoid infinite recursion with
  // cycles. This approach directly extracts immediate
  // dependencies without recursive traversal.
  for (const auto &[id, kind] : id_to_kind) {
    // Copy id to a local variable to workaround a bug in Apple's clang.
    // See: https://github.com/llvm/llvm-project/issues/48582
    auto local_id = id;
    bool match = false;
    if (!filter || (*filter)(local_id)) {
      match = true;
      filtered_types.insert(local_id);
    }

    // Initialize entries for this type
    if (parents.find(local_id) == parents.end()) {
      parents[local_id] = std::set<btf_type_id>();
    }
    if (children.find(local_id) == children.end()) {
      children[local_id] = std::set<btf_type_id>();
    }

    // Directly extract dependencies from the kind without recursive traversal
    std::visit(
        [&](auto k) {
          if constexpr (btf_kind_traits<decltype(k)>::has_type) {
            btf_type_id dep_id = k.type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_index_type) {
            btf_type_id dep_id = k.index_type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_element_type) {
            btf_type_id dep_id = k.element_type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_return_type) {
            btf_type_id dep_id = k.return_type;
            if (dep_id != local_id &&
                id_to_kind.find(dep_id) != id_to_kind.end()) {
              children[local_id].insert(dep_id);
              if (parents.find(dep_id) == parents.end()) {
                parents[dep_id] = std::set<btf_type_id>();
              }
              parents[dep_id].insert(local_id);
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_members) {
            for (auto member : k.members) {
              if constexpr (btf_kind_traits<decltype(member)>::has_type) {
                btf_type_id dep_id = member.type;
                if (dep_id != local_id &&
                    id_to_kind.find(dep_id) != id_to_kind.end()) {
                  children[local_id].insert(dep_id);
                  if (parents.find(dep_id) == parents.end()) {
                    parents[dep_id] = std::set<btf_type_id>();
                  }
                  parents[dep_id].insert(local_id);
                }
              }
            }
          }
          if constexpr (btf_kind_traits<decltype(k)>::has_parameters) {
            for (auto param : k.parameters) {
              if constexpr (btf_kind_traits<decltype(param)>::has_type) {
                btf_type_id dep_id = param.type;
                if (dep_id != local_id &&
                    id_to_kind.find(dep_id) != id_to_kind.end()) {
                  children[local_id].insert(dep_id);
                  if (parents.find(dep_id) == parents.end()) {
                    parents[dep_id] = std::set<btf_type_id>();
                  }
                  parents[dep_id].insert(local_id);
                }
              }
            }
          }
        },
        kind);
  }

  // Perform topological sort with cycle breaking
  // Add safety limit to prevent infinite loops in case of bugs in
  // cycle-breaking logic
  size_t previous_size = 0;
  size_t iteration_count = 0;
  const size_t max_iterations =
      id_to_kind.size() * 3; // Safety limit to prevent infinite loops in cycles

  while (!parents.empty() && iteration_count < max_iterations) {
    iteration_count++;
    std::vector<btf_type_id> types_to_remove;

    // Find all types with no parents.
    for (auto &[id, child_set] : parents) {
      if (child_set.empty()) {
        types_to_remove.push_back(id);
      }
    }

    // If we can't make progress (no types with empty parents),
    // we have cycles. Break them by selecting arbitrary types.
    if (types_to_remove.empty()) {
      // Pick the first type with the fewest dependencies to break the cycle
      btf_type_id min_id = parents.begin()->first;
      size_t min_deps = parents.begin()->second.size();
      for (const auto &[id, deps] : parents) {
        if (deps.size() < min_deps) {
          min_id = id;
          min_deps = deps.size();
        }
      }
      types_to_remove.push_back(min_id);
    }

    if (types_to_remove.empty()) {
      // Safety: force progress if we're still stuck
      types_to_remove.push_back(parents.begin()->first);
    }

    previous_size = parents.size();

    // Remove these parents from all children.
    for (auto id : types_to_remove) {
      for (auto child : children[id]) {
        parents[child].erase(id);
      }
      parents.erase(id);
    }
    // Append these types to the result.
    result.insert(result.end(), types_to_remove.begin(), types_to_remove.end());
  }

  // Remove types that are not children of the filtered type.
  std::vector<btf_type_id> filtered_result;
  for (auto id : result) {
    if (filtered_types.find(id) != filtered_types.end()) {
      filtered_result.push_back(id);
    }
  }

  std::reverse(filtered_result.begin(), filtered_result.end());
  return filtered_result;
}

void btf_type_data::to_c_header(
    std::ostream &out,
    std::optional<std::function<bool(btf_type_id)>> filter) const {
  std::set<btf_type_id> declared_types;

  size_t indent = 0;
  out << "#pragma once\n\n";

  // Print each type in dependency order.
  for (auto id : dependency_order(filter)) {
    if (get_type_name(id).empty()) {
      continue;
    }
    std::visit(
        [&, this](auto kind) {
          if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
            out << "typedef ";
            out << get_type_declaration(kind.type, kind.name, indent)
                << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind),
                                              btf_kind_struct>) {
            out << get_type_declaration(id, "", indent) << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind), btf_kind_union>) {
            out << get_type_declaration(id, "", indent) << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind), btf_kind_fwd>) {
            out << (kind.is_struct ? "union" : "struct ") << kind.name
                << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind), btf_kind_var>) {
            out << get_type_declaration(kind.type, kind.name, indent)
                << ";\n\n";
          } else if constexpr (std::is_same_v<decltype(kind),
                                              btf_kind_function>) {
            if (kind.linkage == BTF_LINKAGE_STATIC) {
              out << "static ";
            } else if (kind.linkage == BTF_LINKAGE_EXTERN) {
              out << "extern ";
            }
            out << get_type_declaration(kind.type, kind.name, indent)
                << ";\n\n";
          }
        },
        get_kind(id));
  }
}

std::string btf_type_data::get_type_name(btf_type_id id) const {
  // Use visit to return the name if the type has it.
  auto kind = get_kind(id);
  return std::visit(
      [](auto kind) -> std::string {
        if constexpr (btf_kind_traits<decltype(kind)>::has_optional_name) {
          return kind.name.value_or("");
        } else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
          return kind.name;
        } else {
          return "";
        }
      },
      get_kind(id));
}

std::string btf_type_data::get_qualified_type_name_with_detector(
    btf_type_id id, cycle_detector &detector) const {
  return detector.with_cycle_detection<std::string>(
      id,
      [this, id, &detector]() -> std::string {
        // Main processing logic - adapted from original but using detector
        auto kind = get_kind(id);
        return std::visit(
            [this, &detector](auto kind) -> std::string {
              // Add possible qualifiers.
              std::string qualifier;
              if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
                qualifier = "const ";
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_volatile>) {
                qualifier = "volatile ";
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_restrict>) {
                qualifier = "restrict ";
              }

              std::string suffix;
              if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
                suffix = "*";
              }

              if constexpr (btf_kind_traits<
                                decltype(kind)>::has_optional_name) {
                return qualifier + kind.name.value_or("") + suffix;
              } else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
                return kind.name + suffix;
              } else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
                return qualifier +
                       this->get_qualified_type_name_with_detector(kind.type,
                                                                   detector) +
                       suffix;
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_void>) {
                return qualifier + "void" + suffix;
              } else {
                return "";
              }
            },
            kind);
      },
      [id]() -> std::string {
        // Cycle detected - return placeholder
        return "/* cyclic type " + std::to_string(id) + " */";
      });
}

btf_type_id btf_type_data::get_descendant_type_id_with_detector(
    btf_type_id id, cycle_detector &detector) const {
  return detector.with_cycle_detection<btf_type_id>(
      id,
      [this, id, &detector]() -> btf_type_id {
        // Main processing logic - same as original but using detector
        return std::visit(
            [id, this, &detector](auto kind) -> btf_type_id {
              if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
                return this->get_descendant_type_id_with_detector(kind.type,
                                                                  detector);
              } else {
                return id;
              }
            },
            get_kind(id));
      },
      [id]() -> btf_type_id {
        // Cycle detected - return current id to break the cycle
        return id;
      });
}

std::string btf_type_data::get_type_declaration(btf_type_id id,
                                                const std::string &name,
                                                size_t indent) const {
  cycle_detector detector;
  return get_type_declaration_with_detector(id, name, indent, detector);
}

std::string btf_type_data::get_type_declaration_with_detector(
    btf_type_id id, const std::string &name, size_t indent,
    cycle_detector &detector) const {
  return detector.with_cycle_detection<std::string>(
      id,
      [this, id, &name, indent, &detector]() -> std::string {
        // Build a string of type qualifiers.
        std::string result = std::string(indent, ' ');
        auto kind = get_kind(id);
        std::visit(
            [&](auto kind) {
              if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
                result += get_type_name(id) + " " + name;
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_array>) {
                auto local_name = name;
                if (!local_name.empty() && local_name[0] == '*') {
                  local_name = "(" + local_name + ")";
                }
                auto local_type = get_type_name(kind.element_type);
                if (local_type.empty()) {
                  local_type = get_type_declaration_with_detector(
                      kind.element_type, "", indent, detector);
                }
                result += local_type + " " + local_name + "[" +
                          std::to_string(kind.count_of_elements) + "]";
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_const>) {
                result += "const " + get_type_declaration_with_detector(
                                         kind.type, name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_volatile>) {
                result += "volatile " + get_type_declaration_with_detector(
                                            kind.type, name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_restrict>) {
                result += "restrict " + get_type_declaration_with_detector(
                                            kind.type, name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_ptr>) {
                result = get_type_declaration_with_detector(
                    kind.type, "*" + name, indent, detector);
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_struct>) {
                if (kind.name.has_value()) {
                  result = "struct " + kind.name.value_or("") + " {\n";
                } else {
                  result = "struct {\n";
                }
                for (auto member : kind.members) {
                  std::string type_name = get_type_name(member.type);
                  if (type_name.empty()) {
                    result += get_type_declaration_with_detector(
                                  member.type, member.name.value_or(""),
                                  indent + 2, detector) +
                              ";\n";
                  } else {
                    result += std::string(indent + 2, ' ') + type_name + " " +
                              member.name.value_or("") + ";\n";
                  }
                }
                result += std::string(indent, ' ') + "}";
                if (!name.empty()) {
                  result += " " + name;
                }
              } else if constexpr (std::is_same_v<decltype(kind),
                                                  btf_kind_union>) {
                if (kind.name.has_value()) {
                  result += "union " + kind.name.value_or("") + " {\n";
                } else {
                  result += "union {\n";
                }
                for (auto member : kind.members) {
                  std::string type_name = get_type_name(member.type);
                  if (type_name.empty()) {
                    result += get_type_declaration_with_detector(
                                  member.type, member.name.value_or(""),
                                  indent + 2, detector) +
                              ";\n";
                  } else {
                    result += std::string(indent + 2, ' ') + type_name + " " +
                              member.name.value_or("") + ";\n";
                  }
                }
                result += std::string(indent, ' ') + "}";
                if (!name.empty()) {
                  result += " " + name;
                }
              } else if constexpr (std::is_same_v<
                                       decltype(kind),
                                       btf_kind_function_prototype>) {
                result += get_qualified_type_name_with_detector(
                              kind.return_type, detector) +
                          " " + name + "(";
                for (auto param : kind.parameters) {
                  result += get_qualified_type_name_with_detector(param.type,
                                                                  detector);
                  if (!param.name.empty()) {
                    result += " " + param.name;
                  }
                  result += ", ";
                }
                if (kind.parameters.size() > 0) {
                  result.pop_back();
                  result.pop_back();
                }
                result += ")";
              } else if constexpr (!btf_kind_traits<decltype(kind)>::has_type) {
                result += get_type_name(id) + " " + name;
              }
            },
            kind);

        return result;
      },
      [this, id, &name, indent]() -> std::string {
        // Cycle detected - return just the type name if available, or a
        // placeholder
        auto type_name = get_type_name(id);
        if (!type_name.empty()) {
          return std::string(indent, ' ') + type_name + " " + name;
        } else {
          return std::string(indent, ' ') + "/* cyclic type " +
                 std::to_string(id) + " */ " + name;
        }
      });
}

} // namespace libbtf

1	// Copyright (c) Prevail Verifier contributors.
2	// SPDX-License-Identifier: MIT
3
4	#include "btf_type_data.h"
5
6	#include "btf.h"
7	#include "btf_json.h"
8	#include "btf_parse.h"
9	#include "btf_write.h"
10	#include "cycle_detector.h"
11
12	#include <algorithm>
13	#include <iomanip>
14	#include <sstream>
15	#include <stdexcept>
16
17	namespace libbtf {
18
19	btf_type_data::btf_type_data(const std::vector<std::byte> &btf_data) {	170✔
20	auto visitor = [&, this](btf_type_id id,	2,374✔
21	const std::optional<std::string> &name,
22	const btf_kind &kind) {	3,664✔
23	this->id_to_kind.insert({id, kind});	2,374✔
24	if (name.has_value()) {	2,374✔
25	this->name_to_id.insert({name.value(), id});	1,290✔
26	}
27	};	2,374✔
28	btf_parse_types(btf_data, visitor);	180✔
29	}	170✔
30
31	btf_type_id btf_type_data::get_id(const std::string &name) const {	398✔
32	auto it = name_to_id.find(name);	199✔
33	if (it == name_to_id.end()) {	398✔
34	return 0;	40✔
35	}
36	return it->second;	318✔
37	}
38
39	btf_kind btf_type_data::get_kind(btf_type_id id) const {	56,388✔
40	auto it = id_to_kind.find(id);	28,194✔
41	if (it == id_to_kind.end()) {	56,388✔
42	throw std::runtime_error("BTF type id not found: " + std::to_string(id));	3✔
43	}
44	return it->second;	84,579✔
45	}
46
47	btf_type_id btf_type_data::dereference_pointer(btf_type_id id) const {	314✔
48	return get_kind_type<btf_kind_ptr>(id).type;	314✔
49	}
50
51	uint32_t btf_type_data::get_size(btf_type_id id) const {	748✔
52	cycle_detector detector;	374✔
53	return get_size_with_detector(id, detector);	1,496✔
54	}	374✔
55
56	uint32_t btf_type_data::get_size_with_detector(btf_type_id id,	1,010✔
57	cycle_detector &detector) const {
58	return detector.with_cycle_detection<uint32_t>(	2,020✔
59	id,
60	[this, id, &detector]() -> uint32_t {	2,016✔
61	// Main processing logic - same as original but using detector
62	return std::visit(	1,008✔
63	[this, id, &detector](auto kind) -> uint32_t {	635✔
64	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
65	return sizeof(void *);	103✔
66	} else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
67	return get_size_with_detector(kind.type, detector);	190✔
68	} else if constexpr (btf_kind_traits<
69	decltype(kind)>::has_size_in_bytes) {
70	return kind.size_in_bytes;	203✔
71	} else if constexpr (std::is_same_v<decltype(kind),
72	btf_kind_array>) {
73	return kind.count_of_elements *	36✔
74	get_size_with_detector(kind.element_type, detector);	72✔
75	} else {
76	return 0;	67✔
77	}
78	},
79	get_kind(id));	2,016✔
80	},
81	[]() -> uint32_t {	1✔
82	// Cycle detected - return 0 to avoid infinite recursion
83	return 0;	1✔
84	});	1,515✔
85	}
86
87	void btf_type_data::to_json(	108✔
88	std::ostream &out,
89	std::optional<std::function<bool(btf_type_id)>> filter) const {
90	btf_type_to_json(id_to_kind, out, filter);	108✔
91	}	108✔
92
93	std::vector<std::byte> btf_type_data::to_bytes() const {	70✔
94	std::vector<btf_kind> kinds;	35✔
95	for (const auto &[id, kind] : id_to_kind) {	918✔
96	kinds.push_back(kind);	848✔
97	}
98	return btf_write_types(kinds);	140✔
99	}	70✔
100
101	void btf_type_data::replace(btf_type_id id, const btf_kind &kind) {	4✔
102	if (id_to_kind.find(id) == id_to_kind.end()) {	4✔
103	throw std::runtime_error("BTF type not found: " + std::to_string(id));	×
104	}
105
106	id_to_kind[id] = kind;	4✔
107	update_name_to_id(id);	4✔
108	}	4✔
109
110	btf_type_id btf_type_data::append(const btf_kind &kind) {	22,884✔
111	if (id_to_kind.size() > UINT32_MAX) {	22,884✔
112	throw std::runtime_error("Too many BTF types");	×
113	}
114	btf_type_id next_id = static_cast<btf_type_id>(id_to_kind.size());	22,884✔
115	id_to_kind.insert({next_id, kind});	22,884✔
116	update_name_to_id(next_id);	22,884✔
117	return next_id;	22,884✔
118	}
119
120	void btf_type_data::update_name_to_id(btf_type_id id) {	22,888✔
121
122	auto name = get_type_name(id);	22,888✔
123	if (!name.empty()) {	22,888✔
124	name_to_id.insert({name, id});	2,466✔
125	}
126	}	22,888✔
127
128	std::vector<btf_type_id> btf_type_data::dependency_order(	52✔
129	std::optional<std::function<bool(btf_type_id)>> filter) const {
130	std::map<btf_type_id, std::set<btf_type_id>> children;	26✔
131	std::map<btf_type_id, std::set<btf_type_id>> parents;	26✔
132	std::set<btf_type_id> filtered_types;	26✔
133	std::vector<btf_type_id> result;	26✔
134
135	// Build list of dependencies manually to avoid infinite recursion with
136	// cycles. This approach directly extracts immediate
137	// dependencies without recursive traversal.
138	for (const auto &[id, kind] : id_to_kind) {	730✔
139	// Copy id to a local variable to workaround a bug in Apple's clang.
140	// See: https://github.com/llvm/llvm-project/issues/48582
141	auto local_id = id;	678✔
142	bool match = false;	339✔
143	if (!filter \|\| (*filter)(local_id)) {	678✔
144	match = true;	339✔
145	filtered_types.insert(local_id);	339✔
146	}
147
148	// Initialize entries for this type
149	if (parents.find(local_id) == parents.end()) {	678✔
150	parents[local_id] = std::set<btf_type_id>();	642✔
151	}
152	if (children.find(local_id) == children.end()) {	678✔
153	children[local_id] = std::set<btf_type_id>();	1,017✔
154	}
155
156	// Directly extract dependencies from the kind without recursive traversal
157	std::visit(	678✔
158	[&](auto k) {	585✔
159	if constexpr (btf_kind_traits<decltype(k)>::has_type) {
160	btf_type_id dep_id = k.type;	302✔
161	if (dep_id != local_id &&	1,787✔
162	id_to_kind.find(dep_id) != id_to_kind.end()) {	1,227✔
163	children[local_id].insert(dep_id);	818✔
164	if (parents.find(dep_id) == parents.end()) {	1,520✔
165	parents[dep_id] = std::set<btf_type_id>();	270✔
166	}
167	parents[dep_id].insert(local_id);	302✔
168	}
169	}
170	if constexpr (btf_kind_traits<decltype(k)>::has_index_type) {
171	btf_type_id dep_id = k.index_type;	68✔
172	if (dep_id != local_id &&	136✔
173	id_to_kind.find(dep_id) != id_to_kind.end()) {	68✔
174	children[local_id].insert(dep_id);	68✔
175	if (parents.find(dep_id) == parents.end()) {	68✔
176	parents[dep_id] = std::set<btf_type_id>();	42✔
177	}
178	parents[dep_id].insert(local_id);	68✔
179	}
180	}
181	if constexpr (btf_kind_traits<decltype(k)>::has_element_type) {
182	btf_type_id dep_id = k.element_type;	68✔
183	if (dep_id != local_id &&	136✔
184	id_to_kind.find(dep_id) != id_to_kind.end()) {	68✔
185	children[local_id].insert(dep_id);	68✔
186	if (parents.find(dep_id) == parents.end()) {	68✔
NEW 187	parents[dep_id] = std::set<btf_type_id>();	×
188	}
189	parents[dep_id].insert(local_id);	68✔
190	}
191	}
192	if constexpr (btf_kind_traits<decltype(k)>::has_return_type) {
193	btf_type_id dep_id = k.return_type;	48✔
194	if (dep_id != local_id &&	96✔
195	id_to_kind.find(dep_id) != id_to_kind.end()) {	48✔
196	children[local_id].insert(dep_id);	48✔
197	if (parents.find(dep_id) == parents.end()) {	48✔
198	parents[dep_id] = std::set<btf_type_id>();	21✔
199	}
200	parents[dep_id].insert(local_id);	48✔
201	}
202	}
203	if constexpr (btf_kind_traits<decltype(k)>::has_members) {
204	for (auto member : k.members) {	360✔
205	if constexpr (btf_kind_traits<decltype(member)>::has_type) {
206	btf_type_id dep_id = member.type;	286✔
207	if (dep_id != local_id &&	572✔
208	id_to_kind.find(dep_id) != id_to_kind.end()) {	286✔
209	children[local_id].insert(dep_id);	286✔
210	if (parents.find(dep_id) == parents.end()) {	286✔
211	parents[dep_id] = std::set<btf_type_id>();	28✔
212	}
213	parents[dep_id].insert(local_id);	286✔
214	}
215	}
216	}
217	}
218	if constexpr (btf_kind_traits<decltype(k)>::has_parameters) {
219	for (auto param : k.parameters) {	94✔
220	if constexpr (btf_kind_traits<decltype(param)>::has_type) {
221	btf_type_id dep_id = param.type;	46✔
222	if (dep_id != local_id &&	92✔
223	id_to_kind.find(dep_id) != id_to_kind.end()) {	46✔
224	children[local_id].insert(dep_id);	46✔
225	if (parents.find(dep_id) == parents.end()) {	46✔
NEW 226	parents[dep_id] = std::set<btf_type_id>();	×
227	}
228	parents[dep_id].insert(local_id);	46✔
229	}
230	}
231	}
232	}
233	},	585✔
234	kind);
235	}
236
237	// Perform topological sort with cycle breaking
238	// Add safety limit to prevent infinite loops in case of bugs in
239	// cycle-breaking logic
240	size_t previous_size = 0;	26✔
241	size_t iteration_count = 0;	26✔
242	const size_t max_iterations =
243	id_to_kind.size() * 3; // Safety limit to prevent infinite loops in cycles	52✔
244
245	while (!parents.empty() && iteration_count < max_iterations) {	362✔
246	iteration_count++;	310✔
247	std::vector<btf_type_id> types_to_remove;	155✔
248
249	// Find all types with no parents.
250	for (auto &[id, child_set] : parents) {	2,910✔
251	if (child_set.empty()) {	2,600✔
252	types_to_remove.push_back(id);	688✔
253	}
254	}
255
256	// If we can't make progress (no types with empty parents),
257	// we have cycles. Break them by selecting arbitrary types.
258	if (types_to_remove.empty()) {	310✔
259	// Pick the first type with the fewest dependencies to break the cycle
260	btf_type_id min_id = parents.begin()->first;	2✔
261	size_t min_deps = parents.begin()->second.size();	1✔
262	for (const auto &[id, deps] : parents) {	6✔
263	if (deps.size() < min_deps) {	4✔
NEW 264	min_id = id;	×
265	min_deps = deps.size();
266	}
267	}
268	types_to_remove.push_back(min_id);	2✔
269	}
270
271	if (types_to_remove.empty()) {	310✔
272	// Safety: force progress if we're still stuck
NEW 273	types_to_remove.push_back(parents.begin()->first);	×
274	}
275
276	previous_size = parents.size();	155✔
277
278	// Remove these parents from all children.
279	for (auto id : types_to_remove) {	1,000✔
280	for (auto child : children[id]) {	1,400✔
281	parents[child].erase(id);	710✔
282	}
283	parents.erase(id);	345✔
284	}
285	// Append these types to the result.
286	result.insert(result.end(), types_to_remove.begin(), types_to_remove.end());	310✔
287	}	155✔
288
289	// Remove types that are not children of the filtered type.
290	std::vector<btf_type_id> filtered_result;	26✔
291	for (auto id : result) {	742✔
292	if (filtered_types.find(id) != filtered_types.end()) {	690✔
293	filtered_result.push_back(id);	690✔
294	}
295	}
296
297	std::reverse(filtered_result.begin(), filtered_result.end());	26✔
298	return filtered_result;	78✔
299	}	26✔
300
301	void btf_type_data::to_c_header(	48✔
302	std::ostream &out,
303	std::optional<std::function<bool(btf_type_id)>> filter) const {
304	std::set<btf_type_id> declared_types;	24✔
305
306	size_t indent = 0;	48✔
307	out << "#pragma once\n\n";	48✔
308
309	// Print each type in dependency order.
310	for (auto id : dependency_order(filter)) {	738✔
311	if (get_type_name(id).empty()) {	999✔
312	continue;	350✔
313	}
314	std::visit(	316✔
315	[&, this](auto kind) {	363✔
316	if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
317	out << "typedef ";	182✔
318	out << get_type_declaration(kind.type, kind.name, indent)	158✔
319	<< ";\n\n";	102✔
320	} else if constexpr (std::is_same_v<decltype(kind),
321	btf_kind_struct>) {
322	out << get_type_declaration(id, "", indent) << ";\n\n";	24✔
323	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_union>) {
324	out << get_type_declaration(id, "", indent) << ";\n\n";	×
325	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_fwd>) {
326	out << (kind.is_struct ? "union" : "struct ") << kind.name	30✔
327	<< ";\n\n";	40✔
328	} else if constexpr (std::is_same_v<decltype(kind), btf_kind_var>) {
329	out << get_type_declaration(kind.type, kind.name, indent)	30✔
330	<< ";\n\n";	45✔
331	} else if constexpr (std::is_same_v<decltype(kind),
332	btf_kind_function>) {
333	if (kind.linkage == BTF_LINKAGE_STATIC) {	48✔
334	out << "static ";	4✔
335	} else if (kind.linkage == BTF_LINKAGE_EXTERN) {	44✔
336	out << "extern ";	×
337	}
338	out << get_type_declaration(kind.type, kind.name, indent)	48✔
339	<< ";\n\n";	72✔
340	}
341	},	247✔
342	get_kind(id));	632✔
343	}	24✔
344	}	48✔
345
346	std::string btf_type_data::get_type_name(btf_type_id id) const {	24,032✔
347	// Use visit to return the name if the type has it.
348	auto kind = get_kind(id);	24,032✔
349	return std::visit(
350	[](auto kind) -> std::string {	12,016✔
351	if constexpr (btf_kind_traits<decltype(kind)>::has_optional_name) {
352	return kind.name.value_or("");	396✔
353	} else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
354	return kind.name;	2,762✔
355	} else {
356	return "";	20,874✔
357	}
358	},
359	get_kind(id));	60,080✔
360	}	12,016✔
361
362	std::string btf_type_data::get_qualified_type_name_with_detector(	138✔
363	btf_type_id id, cycle_detector &detector) const {
364	return detector.with_cycle_detection<std::string>(
365	id,
366	[this, id, &detector]() -> std::string {	276✔
367	// Main processing logic - adapted from original but using detector
368	auto kind = get_kind(id);	138✔
369	return std::visit(
370	[this, &detector](auto kind) -> std::string {	160✔
371	// Add possible qualifiers.
372	std::string qualifier;	69✔
373	if constexpr (std::is_same_v<decltype(kind), btf_kind_const>) {
374	qualifier = "const ";
375	} else if constexpr (std::is_same_v<decltype(kind),
376	btf_kind_volatile>) {
377	qualifier = "volatile ";
378	} else if constexpr (std::is_same_v<decltype(kind),
379	btf_kind_restrict>) {
380	qualifier = "restrict ";
381	}
382
383	std::string suffix;	69✔
384	if constexpr (std::is_same_v<decltype(kind), btf_kind_ptr>) {
385	suffix = "*";	22✔
386	}
387
388	if constexpr (btf_kind_traits<
389	decltype(kind)>::has_optional_name) {
390	return qualifier + kind.name.value_or("") + suffix;	40✔
391	} else if constexpr (btf_kind_traits<decltype(kind)>::has_name) {
392	return kind.name + suffix;	132✔
393	} else if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
394	return qualifier +
395	this->get_qualified_type_name_with_detector(kind.type,
396	detector) +
397	suffix;	110✔
398	} else if constexpr (std::is_same_v<decltype(kind),
399	btf_kind_void>) {
400	return qualifier + "void" + suffix;	30✔
401	} else {
NEW 402	return "";	×
403	}
404	},	69✔
405	kind);	276✔
406	},	69✔
NEW 407	[id]() -> std::string {	×
408	// Cycle detected - return placeholder
NEW 409	return "/* cyclic type " + std::to_string(id) + " */";	×
410	});	276✔
411	}
412
NEW 413	btf_type_id btf_type_data::get_descendant_type_id_with_detector(	×
414	btf_type_id id, cycle_detector &detector) const {
NEW 415	return detector.with_cycle_detection<btf_type_id>(	×
416	id,
NEW 417	[this, id, &detector]() -> btf_type_id {	×
418	// Main processing logic - same as original but using detector
NEW 419	return std::visit(	×
NEW 420	[id, this, &detector](auto kind) -> btf_type_id {	×
421	if constexpr (btf_kind_traits<decltype(kind)>::has_type) {
NEW 422	return this->get_descendant_type_id_with_detector(kind.type,	×
423	detector);
424	} else {
NEW 425	return id;	×
426	}
427	},
NEW 428	get_kind(id));	×
429	},
430	[id]() -> btf_type_id {
431	// Cycle detected - return current id to break the cycle
NEW 432	return id;	×
NEW 433	});	×
434	}
435
436	std::string btf_type_data::get_type_declaration(btf_type_id id,	158✔
437	const std::string &name,
438	size_t indent) const {
439	cycle_detector detector;	79✔
440	return get_type_declaration_with_detector(id, name, indent, detector);	316✔
441	}	79✔
442
443	std::string btf_type_data::get_type_declaration_with_detector(	452✔
444	btf_type_id id, const std::string &name, size_t indent,
445	cycle_detector &detector) const {
446	return detector.with_cycle_detection<std::string>(
447	id,
448	[this, id, &name, indent, &detector]() -> std::string {	1,130✔
449	// Build a string of type qualifiers.
450	std::string result = std::string(indent, ' ');	226✔
451	auto kind = get_kind(id);	452✔
452	std::visit(	452✔
453	[&](auto kind) {	452✔
454	if constexpr (std::is_same_v<decltype(kind), btf_kind_typedef>) {
455	result += get_type_name(id) + " " + name;	1,678✔
456	} else if constexpr (std::is_same_v<decltype(kind),
457	btf_kind_array>) {
458	auto local_name = name;	42✔
459	if (!local_name.empty() && local_name[0] == '*') {	84✔
460	local_name = "(" + local_name + ")";	111✔
461	}
462	auto local_type = get_type_name(kind.element_type);	84✔
463	if (local_type.empty()) {	84✔
464	local_type = get_type_declaration_with_detector(	6✔
465	kind.element_type, "", indent, detector);	552✔
466	}
467	result += local_type + " " + local_name + "[" +	126✔
468	std::to_string(kind.count_of_elements) + "]";
469	} else if constexpr (std::is_same_v<decltype(kind),	42✔
470	btf_kind_const>) {
NEW 471	result += "const " + get_type_declaration_with_detector(	×
472	kind.type, name, indent, detector);
473	} else if constexpr (std::is_same_v<decltype(kind),
474	btf_kind_volatile>) {
NEW 475	result += "volatile " + get_type_declaration_with_detector(	×
476	kind.type, name, indent, detector);
477	} else if constexpr (std::is_same_v<decltype(kind),
478	btf_kind_restrict>) {
NEW 479	result += "restrict " + get_type_declaration_with_detector(	×
480	kind.type, name, indent, detector);
481	} else if constexpr (std::is_same_v<decltype(kind),
482	btf_kind_ptr>) {
483	result = get_type_declaration_with_detector(	210✔
484	kind.type, "*" + name, indent, detector);
485	} else if constexpr (std::is_same_v<decltype(kind),
486	btf_kind_struct>) {
487	if (kind.name.has_value()) {	46✔
488	result = "struct " + kind.name.value_or("") + " {\n";	18✔
489	} else {
490	result = "struct {\n";	17✔
491	}
492	for (auto member : kind.members) {	306✔
493	std::string type_name = get_type_name(member.type);	260✔
494	if (type_name.empty()) {	260✔
495	result += get_type_declaration_with_detector(	219✔
496	member.type, member.name.value_or(""),
497	indent + 2, detector) +
498	";\n";
499	} else {
500	result += std::string(indent + 2, ' ') + type_name + " " +	171✔
501	member.name.value_or("") + ";\n";
502	}
503	}
504	result += std::string(indent, ' ') + "}";	69✔
505	if (!name.empty()) {	46✔
506	result += " " + name;	51✔
507	}
508	} else if constexpr (std::is_same_v<decltype(kind),
509	btf_kind_union>) {
510	if (kind.name.has_value()) {	4✔
NEW 511	result += "union " + kind.name.value_or("") + " {\n";	×
512	} else {
513	result += "union {\n";	2✔
514	}
515	for (auto member : kind.members) {	8✔
516	std::string type_name = get_type_name(member.type);	4✔
517	if (type_name.empty()) {	4✔
518	result += get_type_declaration_with_detector(	6✔
519	member.type, member.name.value_or(""),
520	indent + 2, detector) +
521	";\n";
522	} else {
NEW 523	result += std::string(indent + 2, ' ') + type_name + " " +	×
524	member.name.value_or("") + ";\n";
525	}
526	}
527	result += std::string(indent, ' ') + "}";	6✔
528	if (!name.empty()) {	4✔
NEW 529	result += " " + name;	×
530	}
531	} else if constexpr (std::is_same_v<
532	decltype(kind),
533	btf_kind_function_prototype>) {
534	result += get_qualified_type_name_with_detector(	72✔
535	kind.return_type, detector) +
536	" " + name + "(";
537	for (auto param : kind.parameters) {	94✔
538	result += get_qualified_type_name_with_detector(param.type,	69✔
539	detector);
540	if (!param.name.empty()) {	46✔
541	result += " " + param.name;	69✔
542	}
543	result += ", ";	23✔
544	}
545	if (kind.parameters.size() > 0) {	48✔
546	result.pop_back();	23✔
547	result.pop_back();	23✔
548	}
549	result += ")";	24✔
550	} else if constexpr (!btf_kind_traits<decltype(kind)>::has_type) {
551	result += get_type_name(id) + " " + name;	93✔
552	}
553	},	452✔
554	kind);
555
556	return result;	678✔
557	},	226✔
NEW 558	[this, id, &name, indent]() -> std::string {	×
559	// Cycle detected - return just the type name if available, or a
560	// placeholder
NEW 561	auto type_name = get_type_name(id);	×
NEW 562	if (!type_name.empty()) {	×
NEW 563	return std::string(indent, ' ') + type_name + " " + name;	×
564	} else {
NEW 565	return std::string(indent, ' ') + "/* cyclic type " +	×
NEW 566	std::to_string(id) + " */ " + name;	×
567	}
568	});	904✔
569	}
570
571	} // namespace libbtf

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