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

86.91

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

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