text: /**
   *  @file
   *  @copyright defined in myeosio/LICENSE.txt
   */
  #pragma once
  
  #include <myeosio/chain/types.hpp>
  #include <myeosio/chain/authority.hpp>
  #include <myeosio/chain/exceptions.hpp>
  
  #include <myeosio/utilities/parallel_markers.hpp>
  
  #include <fc/scoped_exit.hpp>
  
  #include <boost/range/algorithm/find.hpp>
  #include <boost/algorithm/cxx11/all_of.hpp>
  
  #include <functional>
  
  namespace myeosio { namespace chain {
  
  namespace detail {
  
     // Order of the template types in the static_variant matters to meta_permission_comparator.
     using meta_permission = static_variant<permission_level_weight, key_weight, wait_weight>;
  
     struct get_weight_visitor {
        using result_type = uint32_t;
  
        template<typename Permission>
        uint32_t operator()( const Permission& permission ) { return permission.weight; }
     };
  
     // Orders permissions descending by weight, and breaks ties with Wait permissions being less than
     // Key permissions which are in turn less than Account permissions
     struct meta_permission_comparator {
        bool operator()( const meta_permission& lhs, const meta_permission& rhs ) const {
           get_weight_visitor scale;
           auto lhs_weight = lhs.visit(scale);
           auto lhs_type   = lhs.which();
           auto rhs_weight = rhs.visit(scale);
           auto rhs_type   = rhs.which();
           return std::tie( lhs_weight, lhs_type ) > std::tie( rhs_weight, rhs_type );
        }
     };
  
     using meta_permission_set = boost::container::flat_multiset<meta_permission, meta_permission_comparator>;
  
  } /// namespace detail
  
     /**
      * @brief This class determines whether a set of signing keys are sufficient to satisfy an authority or not
      *
      * To determine whether an authority is satisfied or not, we first determine which keys have approved of a message, and
      * then determine whether that list of keys is sufficient to satisfy the authority. This class takes a list of keys and
      * provides the @ref satisfied method to determine whether that list of keys satisfies a provided authority.
      *
      * @tparam F A callable which takes a single argument of type @ref AccountPermission and returns the corresponding
      * authority
      */
     template<typename PermissionToAuthorityFunc>
     class authority_checker {
        private:
           PermissionToAuthorityFunc            permission_to_authority;
           const std::function<void()>&         checktime;
           vector<public_key_type>              provided_keys; // Making this a flat_set<public_key_type> causes runtime problems with utilities::filter_data_by_marker for some reason. TODO: Figure out why.
           flat_set<permission_level>           provided_permissions;
           vector<bool>                         _used_keys;
           fc::microseconds                     provided_delay;
           uint16_t                             recursion_depth_limit;
  
        public:
           authority_checker( PermissionToAuthorityFunc            permission_to_authority,
                              uint16_t                             recursion_depth_limit,
                              const flat_set<public_key_type>&     provided_keys,
                              const flat_set<permission_level>&    provided_permissions,
                              fc::microseconds                     provided_delay,
                              const std::function<void()>&         checktime
                           )
           :permission_to_authority(permission_to_authority)
           ,checktime( checktime )
           ,provided_keys(provided_keys.begin(), provided_keys.end())
           ,provided_permissions(provided_permissions)
           ,_used_keys(provided_keys.size(), false)
           ,provided_delay(provided_delay)
           ,recursion_depth_limit(recursion_depth_limit)
           {
              FC_ASSERT( static_cast<bool>(checktime), "checktime cannot be empty" );
           }
  
           enum permission_cache_status {
              being_evaluated,
              permission_unsatisfied,
              permission_satisfied
           };
  
           typedef map<permission_level, permission_cache_status> permission_cache_type;
  
           bool satisfied( const permission_level& permission,
                           fc::microseconds override_provided_delay,
                           permission_cache_type* cached_perms = nullptr
                         )
           {
              auto delay_reverter = fc::make_scoped_exit( [this, delay = provided_delay] () mutable {
                 provided_delay = delay;
              });
  
              provided_delay = override_provided_delay;
  
              return satisfied( permission, cached_perms );
           }
  
           bool satisfied( const permission_level& permission, permission_cache_type* cached_perms = nullptr ) {
              permission_cache_type cached_permissions;
  
              if( cached_perms == nullptr )
                 cached_perms = initialize_permission_cache( cached_permissions );
  
              weight_tally_visitor visitor(*this, *cached_perms, 0);
              return ( visitor(permission_level_weight{permission, 1}) > 0 );
           }
  
           template<typename AuthorityType>
           bool satisfied( const AuthorityType& authority,
                           fc::microseconds override_provided_delay,
                           permission_cache_type* cached_perms = nullptr
                         )
           {
              auto delay_reverter = fc::make_scoped_exit( [this, delay = provided_delay] () mutable {
                 provided_delay = delay;
              });
  
              provided_delay = override_provided_delay;
  
              return satisfied( authority, cached_perms );
           }
  
           template<typename AuthorityType>
           bool satisfied( const AuthorityType& authority, permission_cache_type* cached_perms = nullptr ) {
              permission_cache_type cached_permissions;
  
              if( cached_perms == nullptr )
                 cached_perms = initialize_permission_cache( cached_permissions );
  
              return satisfied( authority, *cached_perms, 0 );
           }
  
           bool all_keys_used() const { return boost::algorithm::all_of_equal(_used_keys, true); }
  
           flat_set<public_key_type> used_keys() const {
              auto range = utilities::filter_data_by_marker(provided_keys, _used_keys, true);
              return {range.begin(), range.end()};
           }
           flat_set<public_key_type> unused_keys() const {
              auto range = utilities::filter_data_by_marker(provided_keys, _used_keys, false);
              return {range.begin(), range.end()};
           }
  
           static optional<permission_cache_status>
           permission_status_in_cache( const permission_cache_type& permissions,
                                       const permission_level& level )
           {
              auto itr = permissions.find( level );
              if( itr != permissions.end() )
                 return itr->second;
  
              itr = permissions.find( {level.actor, permission_name()} );
              if( itr != permissions.end() )
                 return itr->second;
  
              return optional<permission_cache_status>();
           }
  
        private:
           permission_cache_type* initialize_permission_cache( permission_cache_type& cached_permissions ) {
              for( const auto& p : provided_permissions ) {
                 cached_permissions.emplace_hint( cached_permissions.end(), p, permission_satisfied );
              }
              return &cached_permissions;
           }
  
           template<typename AuthorityType>
           bool satisfied( const AuthorityType& authority, permission_cache_type& cached_permissions, uint16_t depth ) {
              // Save the current used keys; if we do not satisfy this authority, the newly used keys aren't actually used
              auto KeyReverter = fc::make_scoped_exit([this, keys = _used_keys] () mutable {
                 _used_keys = keys;
              });
  
              // Sort key permissions and account permissions together into a single set of meta_permissions
              detail::meta_permission_set permissions;
  
              permissions.insert(authority.waits.begin(), authority.waits.end());
              permissions.insert(authority.keys.begin(), authority.keys.end());
              permissions.insert(authority.accounts.begin(), authority.accounts.end());
  
              // Check all permissions, from highest weight to lowest, seeing if provided authorization factors satisfies them or not
              weight_tally_visitor visitor(*this, cached_permissions, depth);
              for( const auto& permission : permissions )
                 // If we've got enough weight, to satisfy the authority, return!
                 if( permission.visit(visitor) >= authority.threshold ) {
                    KeyReverter.cancel();
                    return true;
                 }
              return false;
           }
  
           struct weight_tally_visitor {
              using result_type = uint32_t;
  
              authority_checker&     checker;
              permission_cache_type& cached_permissions;
              uint16_t               recursion_depth;
              uint32_t               total_weight = 0;
  
              weight_tally_visitor(authority_checker& checker, permission_cache_type& cached_permissions, uint16_t recursion_depth)
              :checker(checker)
              ,cached_permissions(cached_permissions)
              ,recursion_depth(recursion_depth)
              {}
  
              uint32_t operator()(const wait_weight& permission) {
                 if( checker.provided_delay >= fc::seconds(permission.wait_sec) ) {
                    total_weight += permission.weight;
                 }
                 return total_weight;
              }
  
              uint32_t operator()(const key_weight& permission) {
                 auto itr = boost::find( checker.provided_keys, permission.key );
                 if( itr != checker.provided_keys.end() ) {
                    checker._used_keys[itr - checker.provided_keys.begin()] = true;
                    total_weight += permission.weight;
                 }
                 return total_weight;
              }
  
              uint32_t operator()(const permission_level_weight& permission) {
                 auto status = authority_checker::permission_status_in_cache( cached_permissions, permission.permission );
                 if( !status ) {
                    if( recursion_depth < checker.recursion_depth_limit ) {
                       bool r = false;
                       typename permission_cache_type::iterator itr = cached_permissions.end();
  
                       bool propagate_error = false;
                       try {
                          auto&& auth = checker.permission_to_authority( permission.permission );
                          propagate_error = true;
                          auto res = cached_permissions.emplace( permission.permission, being_evaluated );
                          itr = res.first;
                          r = checker.satisfied( std::forward<decltype(auth)>(auth), cached_permissions, recursion_depth + 1 );
                       } catch( const permission_query_exception& ) {
                          if( propagate_error )
                             throw;
                          else
                             return total_weight; // if the permission doesn't exist, continue without it
                       }
  
                       if( r ) {
                          total_weight += permission.weight;
                          itr->second = permission_satisfied;
                       } else {
                          itr->second = permission_unsatisfied;
                       }
                    }
                 } else if( *status == permission_satisfied ) {
                    total_weight += permission.weight;
                 }
                 return total_weight;
              }
           };
  
     }; /// authority_checker
  
     template<typename PermissionToAuthorityFunc>
     auto make_auth_checker( PermissionToAuthorityFunc&&          pta,
                             uint16_t                             recursion_depth_limit,
                             const flat_set<public_key_type>&     provided_keys,
                             const flat_set<permission_level>&    provided_permissions = flat_set<permission_level>(),
                             fc::microseconds                     provided_delay = fc::microseconds(0),
                             const std::function<void()>&         _checktime = std::function<void()>()
                           )
     {
        auto noop_checktime = []() {};
        const auto& checktime = ( static_cast<bool>(_checktime) ? _checktime : noop_checktime );
        return authority_checker< PermissionToAuthorityFunc>( std::forward<PermissionToAuthorityFunc>(pta),
                                                              recursion_depth_limit,
                                                              provided_keys,
                                                              provided_permissions,
                                                              provided_delay,
                                                              checktime );
     }
  
  } } // namespace myeosio::chain
  