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      213198 :   DependencyResolverInterface() {}
      32             : 
      33             :   /**
      34             :    * Return a set containing the names of items requested by the object.
      35             :    */
      36             :   virtual const std::set<std::string> & getRequestedItems() = 0;
      37             : 
      38             :   /**
      39             :    * Return a set containing the names of items owned by the object.
      40             :    */
      41             :   virtual const std::set<std::string> & getSuppliedItems() = 0;
      42             : 
      43             :   /**
      44             :    * Given a vector, sort using the getRequested/SuppliedItems sets.
      45             :    */
      46             :   template <typename T>
      47             :   static void sort(typename std::vector<T> & vector);
      48             : 
      49             :   /**
      50             :    * Given a vector, sort using the depth-first search
      51             :    */
      52             :   template <typename T>
      53             :   static void sortDFS(typename std::vector<T> & vector);
      54             : 
      55             :   /**
      56             :    * A helper method for cyclic errors.
      57             :    */
      58             :   template <typename T, typename T2>
      59             :   static void cyclicDependencyError(CyclicDependencyException<T2> & e, const std::string & header);
      60             : };
      61             : 
      62             : template <typename T>
      63             : void
      64     2646978 : DependencyResolverInterface::sort(typename std::vector<T> & vector)
      65             : {
      66     2646978 :   sortDFS(vector);
      67     2646974 : }
      68             : 
      69             : template <typename T>
      70             : void
      71     2646978 : DependencyResolverInterface::sortDFS(typename std::vector<T> & vector)
      72             : {
      73     2646978 :   if (vector.size() <= 1)
      74     2412738 :     return;
      75             : 
      76             :   /**
      77             :    * Class that represents the dependency as a graph
      78             :    */
      79      234240 :   DependencyResolver<T> graph;
      80             : 
      81             :   // Map of suppliers: what is supplied -> by what object
      82      234240 :   std::multimap<std::string, T> suppliers_map;
      83     1028736 :   for (auto & v : vector)
      84             :   {
      85             :     // Whether or not this object supplies something, we will always
      86             :     // add it as a node because we want to make sure that it gets returned
      87      794496 :     graph.addNode(v);
      88             : 
      89     1598325 :     for (const auto & supplied_item : v->getSuppliedItems())
      90      803829 :       suppliers_map.emplace(supplied_item, v);
      91             :   }
      92             : 
      93             :   // build the dependency graph
      94     1028736 :   for (auto & v : vector)
      95      866137 :     for (const auto & requested_item : v->getRequestedItems())
      96             :     {
      97       71641 :       const auto & [begin_it, end_it] = suppliers_map.equal_range(requested_item);
      98      116352 :       for (const auto & [supplier_name, supplier_object] : as_range(begin_it, end_it))
      99             :       {
     100       44711 :         libmesh_ignore(supplier_name);
     101             : 
     102             :         // We allow an object to have a circular dependency within itself; e.g. we choose to
     103             :         // trust a developer knows what they are doing within a single object
     104       44711 :         if (supplier_object != v)
     105       29493 :           graph.addEdge(supplier_object, v);
     106             :       }
     107             :     }
     108             : 
     109      234240 :   const auto & sorted = graph.dfs();
     110             : 
     111             :   // The set here gets unique objects, as it's valid to pass in duplicates
     112             :   mooseAssert(sorted.size() == std::set<T>(vector.begin(), vector.end()).size(), "Size mismatch");
     113             : 
     114      234236 :   vector = sorted;
     115      234244 : }
     116             : 
     117             : template <typename T, typename T2>
     118             : void
     119           4 : DependencyResolverInterface::cyclicDependencyError(CyclicDependencyException<T2> & e,
     120             :                                                    const std::string & header)
     121             : {
     122           4 :   std::ostringstream oss;
     123             : 
     124           4 :   oss << header << ":\n";
     125           4 :   const auto cycle = e.getCyclicDependencies();
     126           4 :   std::vector<std::string> names(cycle.size());
     127          16 :   for (const auto i : index_range(cycle))
     128          12 :     names[i] = static_cast<T>(cycle[i])->name();
     129           4 :   oss << MooseUtils::join(names, " <- ");
     130           4 :   mooseError(oss.str());
     131           0 : }