aboutsummaryrefslogtreecommitdiff
path: root/toolsrc/include
diff options
context:
space:
mode:
Diffstat (limited to 'toolsrc/include')
-rw-r--r--toolsrc/include/PackageSpec.h1
-rw-r--r--toolsrc/include/vcpkg_Dependencies.h46
-rw-r--r--toolsrc/include/vcpkg_Graphs.h127
-rw-r--r--toolsrc/include/vcpkg_Util.h6
-rw-r--r--toolsrc/include/vcpkg_optional.h2
5 files changed, 67 insertions, 115 deletions
diff --git a/toolsrc/include/PackageSpec.h b/toolsrc/include/PackageSpec.h
index 4c3b47365..0d69ac89c 100644
--- a/toolsrc/include/PackageSpec.h
+++ b/toolsrc/include/PackageSpec.h
@@ -25,6 +25,7 @@ namespace vcpkg
};
bool operator==(const PackageSpec& left, const PackageSpec& right);
+ bool operator!=(const PackageSpec& left, const PackageSpec& right);
} //namespace vcpkg
namespace std
diff --git a/toolsrc/include/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
index 0e629ffef..f35250447 100644
--- a/toolsrc/include/vcpkg_Dependencies.h
+++ b/toolsrc/include/vcpkg_Dependencies.h
@@ -16,6 +16,15 @@ namespace vcpkg::Dependencies
std::string to_output_string(RequestType request_type, const CStringView s);
+ struct AnyParagraph
+ {
+ std::vector<PackageSpec> dependencies(const Triplet& triplet) const;
+
+ Optional<StatusParagraph> status_paragraph;
+ Optional<BinaryParagraph> binary_paragraph;
+ Optional<SourceParagraph> source_paragraph;
+ };
+
enum class InstallPlanType
{
UNKNOWN,
@@ -26,27 +35,19 @@ namespace vcpkg::Dependencies
struct InstallPlanAction
{
+ static bool compare_by_name(const InstallPlanAction* left, const InstallPlanAction* right);
+
InstallPlanAction();
- InstallPlanAction(const InstallPlanType& plan_type, const RequestType& request_type, Optional<BinaryParagraph> binary_pgh, Optional<SourceParagraph> source_pgh);
+ explicit InstallPlanAction(const PackageSpec& spec, const AnyParagraph& any_paragraph, const RequestType& request_type);
InstallPlanAction(const InstallPlanAction&) = delete;
InstallPlanAction(InstallPlanAction&&) = default;
InstallPlanAction& operator=(const InstallPlanAction&) = delete;
InstallPlanAction& operator=(InstallPlanAction&&) = default;
+ PackageSpec spec;
+ AnyParagraph any_paragraph;
InstallPlanType plan_type;
RequestType request_type;
- Optional<BinaryParagraph> binary_pgh;
- Optional<SourceParagraph> source_pgh;
- };
-
- struct PackageSpecWithInstallPlan
- {
- static bool compare_by_name(const PackageSpecWithInstallPlan* left, const PackageSpecWithInstallPlan* right);
-
- PackageSpecWithInstallPlan(const PackageSpec& spec, InstallPlanAction&& plan);
-
- PackageSpec spec;
- InstallPlanAction plan;
};
enum class RemovePlanType
@@ -58,28 +59,21 @@ namespace vcpkg::Dependencies
struct RemovePlanAction
{
+ static bool compare_by_name(const RemovePlanAction* left, const RemovePlanAction* right);
+
RemovePlanAction();
- RemovePlanAction(const RemovePlanType& plan_type, const RequestType& request_type);
+ RemovePlanAction(const PackageSpec& spec, const RemovePlanType& plan_type, const RequestType& request_type);
RemovePlanAction(const RemovePlanAction&) = delete;
RemovePlanAction(RemovePlanAction&&) = default;
RemovePlanAction& operator=(const RemovePlanAction&) = delete;
RemovePlanAction& operator=(RemovePlanAction&&) = default;
+ PackageSpec spec;
RemovePlanType plan_type;
RequestType request_type;
};
- struct PackageSpecWithRemovePlan
- {
- static bool compare_by_name(const PackageSpecWithRemovePlan* left, const PackageSpecWithRemovePlan* right);
-
- PackageSpecWithRemovePlan(const PackageSpec& spec, RemovePlanAction&& plan);
-
- PackageSpec spec;
- RemovePlanAction plan;
- };
-
- std::vector<PackageSpecWithInstallPlan> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
+ std::vector<InstallPlanAction> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
- std::vector<PackageSpecWithRemovePlan> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
+ std::vector<RemovePlanAction> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
}
diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h
index 933d9ac67..97cd29236 100644
--- a/toolsrc/include/vcpkg_Graphs.h
+++ b/toolsrc/include/vcpkg_Graphs.h
@@ -1,7 +1,6 @@
#pragma once
#include <unordered_map>
-#include <unordered_set>
namespace vcpkg::Graphs
{
@@ -17,104 +16,54 @@ namespace vcpkg::Graphs
FULLY_EXPLORED
};
- template <class V>
- class Graph
+ template <class V, class U>
+ __interface AdjacencyProvider
{
- static void find_topological_sort_internal(V vertex,
- ExplorationStatus& status,
- const std::unordered_map<V, std::unordered_set<V>>& adjacency_list,
- std::unordered_map<V, ExplorationStatus>& exploration_status,
- std::vector<V>& sorted)
- {
- status = ExplorationStatus::PARTIALLY_EXPLORED;
-
- for (V neighbour : adjacency_list.at(vertex))
- {
- ExplorationStatus& neighbour_status = exploration_status[neighbour];
- if (neighbour_status == ExplorationStatus::NOT_EXPLORED)
- {
- find_topological_sort_internal(neighbour, neighbour_status, adjacency_list, exploration_status, sorted);
- }
- else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED)
- {
- throw std::runtime_error("cycle in graph");
- }
- }
-
- status = ExplorationStatus::FULLY_EXPLORED;
- sorted.push_back(vertex);
- }
+ std::vector<V> adjacency_list(const U& vertex) const;
- public:
-
- void add_vertex(V v)
- {
- this->vertices[v];
- }
-
- // TODO: Change with iterators
- void add_vertices(const std::vector<V>& vs)
- {
- for (const V& v : vs)
- {
- this->vertices[v];
- }
- }
-
- void add_edge(V u, V v)
- {
- this->vertices[v];
- this->vertices[u].insert(v);
- }
+ U load_vertex_data(const V& vertex) const;
+ };
- std::vector<V> find_topological_sort() const
+ template <class V, class U>
+ static void topological_sort_internal(const V& vertex,
+ const AdjacencyProvider<V, U>& f,
+ std::unordered_map<V, ExplorationStatus>& exploration_status,
+ std::vector<U>& sorted)
+ {
+ ExplorationStatus& status = exploration_status[vertex];
+ switch (status)
{
- std::unordered_map<V, int> indegrees = count_indegrees();
-
- std::vector<V> sorted;
- sorted.reserve(indegrees.size());
-
- std::unordered_map<V, ExplorationStatus> exploration_status;
- exploration_status.reserve(indegrees.size());
-
- for (auto& pair : indegrees)
- {
- if (pair.second == 0) // Starting from vertices with indegree == 0. Not required.
+ case ExplorationStatus::FULLY_EXPLORED:
+ return;
+ case ExplorationStatus::PARTIALLY_EXPLORED:
+ Checks::exit_with_message(VCPKG_LINE_INFO, "cycle in graph");
+ case ExplorationStatus::NOT_EXPLORED:
{
- V vertex = pair.first;
- ExplorationStatus& status = exploration_status[vertex];
- if (status == ExplorationStatus::NOT_EXPLORED)
- {
- find_topological_sort_internal(vertex, status, this->vertices, exploration_status, sorted);
- }
+ status = ExplorationStatus::PARTIALLY_EXPLORED;
+ U vertex_data = f.load_vertex_data(vertex);
+ for (const V& neighbour : f.adjacency_list(vertex_data))
+ topological_sort_internal(neighbour, f, exploration_status, sorted);
+
+ sorted.push_back(std::move(vertex_data));
+ status = ExplorationStatus::FULLY_EXPLORED;
+ return;
}
- }
-
- return sorted;
+ default:
+ Checks::unreachable(VCPKG_LINE_INFO);
}
+ }
- std::unordered_map<V, int> count_indegrees() const
- {
- std::unordered_map<V, int> indegrees;
-
- for (auto& pair : this->vertices)
- {
- indegrees[pair.first];
- for (V neighbour : pair.second)
- {
- ++indegrees[neighbour];
- }
- }
-
- return indegrees;
- }
+ template <class V, class U>
+ std::vector<U> topological_sort(const std::vector<V>& starting_vertices, const AdjacencyProvider<V, U>& f)
+ {
+ std::vector<U> sorted;
+ std::unordered_map<V, ExplorationStatus> exploration_status;
- const std::unordered_map<V, std::unordered_set<V>>& adjacency_list() const
+ for (auto& vertex : starting_vertices)
{
- return this->vertices;
+ topological_sort_internal(vertex, f, exploration_status, sorted);
}
- private:
- std::unordered_map<V, std::unordered_set<V>> vertices;
- };
+ return sorted;
+ }
}
diff --git a/toolsrc/include/vcpkg_Util.h b/toolsrc/include/vcpkg_Util.h
index cd8dab437..c717830f0 100644
--- a/toolsrc/include/vcpkg_Util.h
+++ b/toolsrc/include/vcpkg_Util.h
@@ -27,4 +27,10 @@ namespace vcpkg::Util
{
cont.erase(std::partition(cont.begin(), cont.end(), pred), cont.end());
}
+
+ template<class Container, class Pred>
+ void keep_if(Container& cont, Pred pred)
+ {
+ cont.erase(std::remove_if(cont.begin(), cont.end(), pred), cont.end());
+ }
} \ No newline at end of file
diff --git a/toolsrc/include/vcpkg_optional.h b/toolsrc/include/vcpkg_optional.h
index 4a2ceec30..28bdc81fa 100644
--- a/toolsrc/include/vcpkg_optional.h
+++ b/toolsrc/include/vcpkg_optional.h
@@ -15,6 +15,8 @@ namespace vcpkg
class Optional
{
public:
+ constexpr Optional() : m_is_present(false), m_t() { }
+
// Constructors are intentionally implicit
constexpr Optional(NullOpt) : m_is_present(false), m_t() { }
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-10 19:29:50 +0000