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      235018 :   DependencyResolverInterface() {}
      32             : 
      33             : #ifdef MOOSE_KOKKOS_ENABLED
      34             :   /**
      35             :    * Special constructor used for Kokkos functor copy during parallel dispatch
      36             :    */
      37      113369 :   DependencyResolverInterface(const DependencyResolverInterface &,
      38             :                               const Moose::Kokkos::FunctorCopy &)
      39      113369 :   {
      40      113369 :   }
      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, typename NameFunc>
      69             :   static void cyclicDependencyError(CyclicDependencyException<T2> & e,
      70             :                                     const std::string & header,
      71             :                                     NameFunc && name_func);
      72             : 
      73             :   template <typename T, typename T2>
      74             :   static void cyclicDependencyError(CyclicDependencyException<T2> & e, const std::string & header);
      75             : };
      76             : 
      77             : template <typename T>
      78             : void
      79     2787275 : DependencyResolverInterface::sort(typename std::vector<T> & vector)
      80             : {
      81     2787275 :   sortDFS(vector);
      82     2787270 : }
      83             : 
      84             : template <typename T>
      85             : void
      86     2787275 : DependencyResolverInterface::sortDFS(typename std::vector<T> & vector)
      87             : {
      88     2787275 :   if (vector.size() <= 1)
      89     2528684 :     return;
      90             : 
      91             :   /**
      92             :    * Class that represents the dependency as a graph
      93             :    */
      94      258591 :   DependencyResolver<T> graph;
      95             : 
      96             :   // Map of suppliers: what is supplied -> by what object
      97      258591 :   std::multimap<std::string, T> suppliers_map;
      98     1112717 :   for (auto & v : vector)
      99             :   {
     100             :     // Whether or not this object supplies something, we will always
     101             :     // add it as a node because we want to make sure that it gets returned
     102      854126 :     graph.addNode(v);
     103             : 
     104     1717953 :     for (const auto & supplied_item : v->getSuppliedItems())
     105      863827 :       suppliers_map.emplace(supplied_item, v);
     106             :   }
     107             : 
     108             :   // build the dependency graph
     109     1112717 :   for (auto & v : vector)
     110      929985 :     for (const auto & requested_item : v->getRequestedItems())
     111             :     {
     112       75859 :       const auto & [begin_it, end_it] = suppliers_map.equal_range(requested_item);
     113      123679 :       for (const auto & [supplier_name, supplier_object] : as_range(begin_it, end_it))
     114             :       {
     115       47820 :         libmesh_ignore(supplier_name);
     116             : 
     117             :         // We allow an object to have a circular dependency within itself; e.g. we choose to
     118             :         // trust a developer knows what they are doing within a single object
     119       47820 :         if (supplier_object != v)
     120       34452 :           graph.addEdge(supplier_object, v);
     121             :       }
     122             :     }
     123             : 
     124      258591 :   const auto & sorted = graph.dfs();
     125             : 
     126             :   // The set here gets unique objects, as it's valid to pass in duplicates
     127             :   mooseAssert(sorted.size() == std::set<T>(vector.begin(), vector.end()).size(), "Size mismatch");
     128             : 
     129      258586 :   vector = sorted;
     130      258596 : }
     131             : 
     132             : template <typename T, typename T2, typename NameFunc>
     133             : void
     134           5 : DependencyResolverInterface::cyclicDependencyError(CyclicDependencyException<T2> & e,
     135             :                                                    const std::string & header,
     136             :                                                    NameFunc && name_func)
     137             : {
     138           5 :   std::ostringstream oss;
     139             : 
     140           5 :   oss << header << ":\n";
     141           5 :   const auto cycle = e.getCyclicDependencies();
     142           5 :   std::vector<std::string> names(cycle.size());
     143          20 :   for (const auto i : index_range(cycle))
     144          15 :     names[i] = name_func(cycle[i]);
     145           5 :   oss << MooseUtils::join(names, " <- ");
     146           5 :   mooseError(oss.str());
     147           0 : }
     148             : 
     149             : template <typename T, typename T2>
     150             : void
     151           5 : DependencyResolverInterface::cyclicDependencyError(CyclicDependencyException<T2> & e,
     152             :                                                    const std::string & header)
     153             : {
     154          20 :   cyclicDependencyError<T>(e, header, [](const auto & obj) { return static_cast<T>(obj)->name(); });
     155           0 : }