winget-cli

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README | LICENSE

DependenciesGraph.cpp (4411B)

      1 // Copyright (c) Microsoft Corporation.
      2 // Licensed under the MIT License.
      3 #include "pch.h"
      4 #include "winget\DependenciesGraph.h"
      5 
      6 namespace AppInstaller::Manifest
      7 {
      8     // this constructor was intented for use during installation flow (we already have installer dependencies and there's no need to search the source again)
      9     DependencyGraph::DependencyGraph(const Dependency& root, const DependencyList& rootDependencies,
     10         std::function<const DependencyList(const Dependency&)> infoFunction) : m_root(root), getDependencies(infoFunction)
     11     {
     12         m_adjacents[m_root] = std::set<Dependency>();
     13         m_toCheck = std::vector<Dependency>();
     14         rootDependencies.ApplyToType(DependencyType::Package, [&](Dependency dependency)
     15             {
     16                 m_toCheck.push_back(dependency);
     17                 AddNode(dependency);
     18                 AddAdjacent(root, dependency);
     19             });
     20         m_rootDependencyEvaluated = true;
     21     }
     22 
     23     DependencyGraph::DependencyGraph(const Dependency& root, std::function<const DependencyList(const Dependency&)> infoFunction) : m_root(root), getDependencies(infoFunction)
     24     {
     25         m_adjacents[m_root] = std::set<Dependency>();
     26         m_toCheck = std::vector<Dependency>();
     27     }
     28 
     29     void DependencyGraph::BuildGraph()
     30     {
     31         if (!m_rootDependencyEvaluated) 
     32         {
     33             const DependencyList& rootDependencies = getDependencies(m_root);
     34             rootDependencies.ApplyToType(DependencyType::Package, [&](Dependency dependency)
     35                 {
     36                     m_toCheck.push_back(dependency);
     37                     AddNode(dependency);
     38                     AddAdjacent(m_root, dependency);
     39                 });
     40             m_rootDependencyEvaluated = true;
     41         }
     42 
     43         if (m_toCheck.empty())
     44         {
     45             return;
     46         }
     47 
     48         for (unsigned int i = 0; i < m_toCheck.size(); ++i)
     49         {
     50             auto node = m_toCheck.at(i);
     51 
     52             const auto& nodeDependencies = getDependencies(node);
     53             nodeDependencies.ApplyToType(DependencyType::Package, [&](Dependency dependency)
     54                 {
     55                     if (!HasNode(dependency))
     56                     {
     57                         m_toCheck.push_back(dependency);
     58                         AddNode(dependency);
     59                     }
     60 
     61                     AddAdjacent(node, dependency);
     62                 });
     63         }
     64 
     65         CheckForLoopsAndGetOrder();
     66     }
     67 
     68     void DependencyGraph::AddNode(const Dependency& node)
     69     {
     70         m_adjacents[node] = std::set<Dependency>();
     71     }
     72 
     73     void DependencyGraph::AddAdjacent(const Dependency& node, const Dependency& adjacent)
     74     {
     75         m_adjacents[node].emplace(adjacent);
     76     }
     77 
     78     bool DependencyGraph::HasNode(const Dependency& dependency)
     79     {
     80         auto search = m_adjacents.find(dependency);
     81         return search != m_adjacents.end();
     82     }
     83 
     84     bool DependencyGraph::HasLoop()
     85     {
     86         return m_HasLoop;
     87     }
     88 
     89     void DependencyGraph::CheckForLoopsAndGetOrder()
     90     {
     91         m_installationOrder = std::vector<Dependency>();
     92         std::set<Dependency> visited;
     93         m_HasLoop = HasLoopDFS(visited, m_root);
     94     }
     95 
     96     std::vector<Dependency> DependencyGraph::GetInstallationOrder()
     97     {
     98         return m_installationOrder;
     99     }
    100 
    101     // TODO make this function iterative
    102     bool DependencyGraph::HasLoopDFS(std::set<Dependency> visited, const Dependency& node)
    103     {
    104         bool loop = false;
    105 
    106         visited.insert(node);
    107         auto lAdjacents = m_adjacents.at(node);
    108         for (const auto& adjacent : m_adjacents.at(node))
    109         {
    110             auto search = visited.find(adjacent);
    111             if (search == visited.end()) // if not found
    112             {
    113                 if (HasLoopDFS(visited, adjacent))
    114                 {
    115                     loop = true;
    116                     // didn't break the loop to have a complete order at the end (even if a loop exists)
    117                 }
    118             }
    119             else
    120             {
    121                 loop = true;
    122                 // didn't break the loop to have a complete order at the end (even if a loop exists)
    123             }
    124         }
    125 
    126         // Adding to have an order even if a loop is present
    127         if (std::find(m_installationOrder.begin(), m_installationOrder.end(), node) == m_installationOrder.end())
    128         {
    129             m_installationOrder.push_back(node);
    130         }
    131 
    132         return loop;
    133     }
    134 }