Line data    Source code

       1             : //* This file is part of the MOOSE framework
       2             : //* https://mooseframework.inl.gov
       3             : //*
       4             : //* All rights reserved, see COPYRIGHT for full restrictions
       5             : //* https://github.com/idaholab/moose/blob/master/COPYRIGHT
       6             : //*
       7             : //* Licensed under LGPL 2.1, please see LICENSE for details
       8             : //* https://www.gnu.org/licenses/lgpl-2.1.html
       9             : 
      10             : #pragma once
      11             : 
      12             : // STL includes
      13             : #include <string>
      14             : #include <set>
      15             : #include <iostream>
      16             : #include <algorithm>
      17             : 
      18             : // MOOSE includes
      19             : #include "DependencyResolver.h"
      20             : #include "MooseUtils.h"
      21             : 
      22             : /**
      23             :  * Interface for sorting dependent vectors of objects.
      24             :  */
      25             : class DependencyResolverInterface
      26             : {
      27             : public:
      28             :   /**
      29             :    * Constructor.
      30             :    */
      31      239132 :   DependencyResolverInterface() {}
      32             : 
      33             : #ifdef MOOSE_KOKKOS_ENABLED
      34             :   /**
      35             :    * Special constructor used for Kokkos functor copy during parallel dispatch
      36             :    */
      37       37959 :   DependencyResolverInterface(const DependencyResolverInterface &,
      38             :                               const Moose::Kokkos::FunctorCopy &)
      39       37959 :   {
      40       37959 :   }
      41             : #endif
      42             : 
      43             :   /**
      44             :    * Return a set containing the names of items requested by the object.
      45             :    */
      46             :   virtual const std::set<std::string> & getRequestedItems() = 0;
      47             : 
      48             :   /**
      49             :    * Return a set containing the names of items owned by the object.
      50             :    */
      51             :   virtual const std::set<std::string> & getSuppliedItems() = 0;
      52             : 
      53             :   /**
      54             :    * Given a vector, sort using the getRequested/SuppliedItems sets.
      55             :    */
      56             :   template <typename T>
      57             :   static void sort(typename std::vector<T> & vector);
      58             : 
      59             :   /**
      60             :    * Given a vector, sort using the depth-first search
      61             :    */
      62             :   template <typename T>
      63             :   static void sortDFS(typename std::vector<T> & vector);
      64             : 
      65             :   /**
      66             :    * A helper method for cyclic errors.
      67             :    */
      68             :   template <typename T, typename T2>
      69             :   static void cyclicDependencyError(CyclicDependencyException<T2> & e, const std::string & header);
      70             : };
      71             : 
      72             : template <typename T>
      73             : void
      74     2986425 : DependencyResolverInterface::sort(typename std::vector<T> & vector)
      75             : {
      76     2986425 :   sortDFS(vector);
      77     2986419 : }
      78             : 
      79             : template <typename T>
      80             : void
      81     2986425 : DependencyResolverInterface::sortDFS(typename std::vector<T> & vector)
      82             : {
      83     2986425 :   if (vector.size() <= 1)
      84     2724233 :     return;
      85             : 
      86             :   /**
      87             :    * Class that represents the dependency as a graph
      88             :    */
      89      262192 :   DependencyResolver<T> graph;
      90             : 
      91             :   // Map of suppliers: what is supplied -> by what object
      92      262192 :   std::multimap<std::string, T> suppliers_map;
      93     1150204 :   for (auto & v : vector)
      94             :   {
      95             :     // Whether or not this object supplies something, we will always
      96             :     // add it as a node because we want to make sure that it gets returned
      97      888012 :     graph.addNode(v);
      98             : 
      99     1785972 :     for (const auto & supplied_item : v->getSuppliedItems())
     100      897960 :       suppliers_map.emplace(supplied_item, v);
     101             :   }
     102             : 
     103             :   // build the dependency graph
     104     1150204 :   for (auto & v : vector)
     105      973592 :     for (const auto & requested_item : v->getRequestedItems())
     106             :     {
     107       85580 :       const auto & [begin_it, end_it] = suppliers_map.equal_range(requested_item);
     108      142148 :       for (const auto & [supplier_name, supplier_object] : as_range(begin_it, end_it))
     109             :       {
     110       56568 :         libmesh_ignore(supplier_name);
     111             : 
     112             :         // We allow an object to have a circular dependency within itself; e.g. we choose to
     113             :         // trust a developer knows what they are doing within a single object
     114       56568 :         if (supplier_object != v)
     115       40020 :           graph.addEdge(supplier_object, v);
     116             :       }
     117             :     }
     118             : 
     119      262192 :   const auto & sorted = graph.dfs();
     120             : 
     121             :   // The set here gets unique objects, as it's valid to pass in duplicates
     122             :   mooseAssert(sorted.size() == std::set<T>(vector.begin(), vector.end()).size(), "Size mismatch");
     123             : 
     124      262186 :   vector = sorted;
     125      262198 : }
     126             : 
     127             : template <typename T, typename T2>
     128             : void
     129           6 : DependencyResolverInterface::cyclicDependencyError(CyclicDependencyException<T2> & e,
     130             :                                                    const std::string & header)
     131             : {
     132           6 :   std::ostringstream oss;
     133             : 
     134           6 :   oss << header << ":\n";
     135           6 :   const auto cycle = e.getCyclicDependencies();
     136           6 :   std::vector<std::string> names(cycle.size());
     137          24 :   for (const auto i : index_range(cycle))
     138          18 :     names[i] = static_cast<T>(cycle[i])->name();
     139           6 :   oss << MooseUtils::join(names, " <- ");
     140           6 :   mooseError(oss.str());
     141           0 : }