cseoptimization.hh

#ifndef __DUNE_ACFEM_EXPRESSIONS_CSEOPTIMIZATION_HH__
#define __DUNE_ACFEM_EXPRESSIONS_CSEOPTIMIZATION_HH__
 
#include "../common/ostream.hh"
#include "../mpl/subtuple.hh"
#include "../mpl/compare.hh"
#include "../mpl/typetupleutil.hh"
#include "examineutil.hh"
#include "extract.hh"
#include "treeextract.hh"
#include "optimizationbase.hh"
#include "runtimeequal.hh"
#include "subexpression.hh"
 
namespace Dune {
 
  namespace ACFem {
 
    namespace Expressions {
 
      using ACFem::operator==;
 
      //
      template<class Expr, template<class...> class IsCandidate, std::ptrdiff_t N = -1>
      struct IsSubExpressionCandidate
      {
        //T is a MPL::TypeTuple<Expr, TreePos, Parent>.
        template<class T, class Parent, class SFINAE = void>
        struct Predicate
          : IsCandidate<T, Parent, Expr>
        {};
 
        //Restrict to the given expression depth.
        template<class T, class Parent>
        struct Predicate<T, Parent,
                         std::enable_if_t<std::is_same<Parent, void>::value || (N != -1 && Depth<T>::value != (std::size_t)N)> >
          : FalseType
        {};
 
        template<class T>
        using Ignore = BoolConstant<IsSelfExpression<T>::value || (Depth<T>::value < N)>;
      };
 
      template<class T, class SExp, class SFINAE = void>
      struct IsMatchingSubExpression
        : FalseType
      {};
 
      template<class T, class SExp>
      struct IsMatchingSubExpression<
        T,
        SExp,
        std::enable_if_t<(IsSubExpressionExpression<T>::value
                          && AreRuntimeEqual<Operand<1, T>, Operand<1, SExp> >::value
        )> >
          : TrueType
      {};
 
      template<class Traits, class DepthTuple>
      class CommonSubExpressionCascade;
 
      template<class T, class SFINAE = void>
      struct IsCSECascade
        : FalseType
      {};
 
      template<class T>
      struct IsCSECascade<T, std::enable_if_t<!IsDecay<T>::value> >
        : IsCSECascade<std::decay_t<T> >
      {};
 
      template<class Traits, class DepthTuple>
      struct IsCSECascade<CommonSubExpressionCascade<Traits, DepthTuple> >
        : TrueType
      {};
 
      /**********************************************************************
       *
       * Loop over a hierarchy of subexpressions. Think about a nested
       * tuple of tuples. The inner tuples conatain a unique set of
       * sub-expression for a given expression depth.
       *
       * The expressions in the higher-depth tuples may contain
       * referencews to sub-expressions at lower level.
       *
       * There are two tasks:
       *
       * + generate such a nested structure from a given expression
       *   template.
       *
       * + if the structure has been built then copy constructions
       *   needs adjustment of the contained references.
       *
       */
 
      namespace {
        // helper functions for class construction
 
        template<template<class...> class P>
        struct OrMatchTreePos
        {
          template<class T1, class T2, class SFINAE = void>
          struct Predicate;
 
          template<class E, class TreePos, class SExp>
          struct Predicate<
            MPL::TypeTuple<E, TreePos>, SExp, std::enable_if_t<IsSubExpressionExpression<SExp>::value> >
            : BoolConstant<(P<E, SExp>::value || std::is_same<TreePos, typename SubExpressionTraits<SExp>::TreePos>::value)>
          {};
        };
 
        // Endpoint for one level.
        template<template<class...> class MatchPredicate, class SExp, class TreePos, class PrevDepth>
        constexpr decltype(auto) injectSubExpressionsOneLevel(
          SExp&& sExp, TreePos, PrevDepth&& prevDepth, IndexSequence<>)
        {
          return forwardReturnValue<SExp>(sExp);
        }
 
        // Recursion at one level.
        template<template<class...> class MatchPredicate, class SExp, class TreePos, class Traits, class PrevDepth, std::size_t I0, std::size_t... ArgIdx>
        constexpr auto injectSubExpressionsOneLevel(
          SExp&& sExp,
          TreePos,
          const CommonSubExpressionCascade<Traits, PrevDepth>& prevDepth,
          IndexSequence<I0, ArgIdx...>)
        {
          return injectSubExpressionsOneLevel<MatchPredicate>(
            replaceMatching<OrMatchTreePos<MatchPredicate>::template Predicate, IsSubExpressionExpression>(
                           std::forward<SExp>(sExp), std::get<I0>(prevDepth.get()), DontOptimize{}, TreePos{}),
            TreePos{},
            prevDepth,
            IndexSequence<ArgIdx...>{});
        }
 
        // Recursion endpoint at lowest level.
        template<template<class...> class MatchPredicate, class SExp, class Traits, class TreePos, std::enable_if_t<IsExpression<SExp>::value, int> = 0>
        constexpr decltype(auto) injectSubExpressionsRecursion(
          SExp&& sExp,
          TreePos,
          const CommonSubExpressionCascade<Traits, std::tuple<std::tuple<> > >& prevDepth)
        {
          return forwardReturnValue<SExp>(sExp);
        }
 
        // Recursion to previous level.
        template<template<class...> class MatchPredicate, class SExp, class TreePos, class Traits, class PrevDepth, class... PrevDepthRest,
                 std::enable_if_t<(IsExpression<SExp>::value && sizeof...(PrevDepthRest) > 0), int> = 0>
        constexpr decltype(auto) injectSubExpressionsRecursion(
          SExp&& sExp,
          TreePos,
          const CommonSubExpressionCascade<Traits, std::tuple<PrevDepth, PrevDepthRest...> >& prevDepth)
        {
          using PrevProvider = CommonSubExpressionCascade<Traits, std::tuple<PrevDepthRest...> >;
 
          // First replace this level subexpressions into sExp.
          auto thisLevel = injectSubExpressionsOneLevel<MatchPredicate>(std::forward<SExp>(sExp),
                                                                        TreePos{},
                                                                        prevDepth,
                                                                        MakeSequenceFor<PrevDepth>{});
          // Then recurse to lower levels
          return injectSubExpressionsRecursion<MatchPredicate>(asExpression(std::move(thisLevel)), TreePos{}, static_cast<const PrevProvider&>(prevDepth));
        }
 
        // Expander, replacing matching expressions by the provided
        // sub-expressions.
        template<class Tuple, class Traits, class PrevDepth, std::size_t... Idx>
        constexpr auto injectSubExpressionsExpander(
          Tuple&& tuple,
          const CommonSubExpressionCascade<Traits, PrevDepth>& prevDepth,
          IndexSequence<Idx...>)
        {
          return std::make_tuple(
            asExpression(
              subExpression<Traits::template Storage>(
                injectSubExpressionsRecursion<AreRuntimeEqual>(
                  std::move(std::get<Idx>(std::forward<Tuple>(tuple)).first),
                  std::get<Idx>(std::forward<Tuple>(tuple)).second, // TreePosition Id
                  prevDepth
                  ),
                std::get<Idx>(std::forward<Tuple>(tuple)).second
                )
              )...
            );
        }
 
        // Expander replacing all existing sub-expressions with the
        // provided ones.
        template<class Tuple, class Traits, class PrevDepth, std::size_t... Idx>
        constexpr auto replaceSubExpressionsExpander(
          Tuple&& tuple,
          const CommonSubExpressionCascade<Traits, PrevDepth>& prevDepth,
          IndexSequence<Idx...>)
        {
          return std::make_tuple(
            asExpression(
              subExpression<Traits::template Storage>(
                injectSubExpressionsRecursion<IsMatchingSubExpression>(
                  std::move(std::get<Idx>(std::forward<Tuple>(tuple)).operand(1_c)),
                  typename SubExpressionTraits<TupleElement<Idx, Tuple> >::TreePos{},
                  prevDepth
                  ),
                typename SubExpressionTraits<TupleElement<Idx, Tuple> >::TreePos{}
                )
              )...
            );
        }
      } // NS anonymous
 
      template<class T, class... SExpNode, class Traits, class PrevDepth>
      constexpr auto injectSubExpressions(T&& t, MPL::TypeTuple<SExpNode...>, const CommonSubExpressionCascade<Traits, PrevDepth>& prevDepth)
      {
        return std::make_tuple(
          asExpression(
            subExpression<Traits::template Storage>(
              injectSubExpressionsRecursion<AreRuntimeEqual>(
                std::move(treeOperand(std::forward<T>(t), typename SExpNode::Second{})),
                typename SExpNode::Second{},
                prevDepth
                ),
              typename SExpNode::Second{}
              )
            )...
          );
      }
 
      template<class Expr, class Traits, class Cascade, class TreePos = IndexSequence<>,
               std::enable_if_t<!IsTupleLike<Expr>::value, int> = 0>
      constexpr auto injectSubExpressions(Expr&& expr, const CommonSubExpressionCascade<Traits, Cascade>& cascade, TreePos = TreePos{})
      {
        return expressionClosure(injectSubExpressionsRecursion<AreRuntimeEqual>(
                                   asExpression(std::forward<Expr>(expr)),
                                   TreePos{},
                                   cascade));
      }
 
      template<class T, class Traits, class PrevDepth, std::enable_if_t<IsTupleLike<T>::value, int> = 0>
      constexpr auto replaceSubExpressions(T&& tuple,
                                           const CommonSubExpressionCascade<Traits, PrevDepth>& prevDepth)
      {
        return replaceSubExpressionsExpander(std::forward<T>(tuple), prevDepth, MakeSequenceFor<T>{});
      }
 
      template<class Expr, class Traits, class Cascade, class TreePos = IndexSequence<>,
               std::enable_if_t<!IsTupleLike<Expr>::value, int> = 0>
      constexpr auto replaceSubExpressions(Expr&& expr, const CommonSubExpressionCascade<Traits, Cascade>& cascade, TreePos = TreePos{})
      {
        return expressionClosure(injectSubExpressionsRecursion<IsMatchingSubExpression>(
                                   asExpression(std::forward<Expr>(expr)),
                                   TreePos{},
                                   cascade));
      }
 
      /*
       *
       **********************************************************************/
 
      template<class Traits>
      class CommonSubExpressionCascade<Traits, std::tuple<std::tuple<> > >
      {
        static constexpr std::size_t depth_ = 0;
       public:
        using DepthType = std::tuple<>;
        using DepthTupleType = std::tuple<DepthType>;
        using TraitsType = Traits;
 
        CommonSubExpressionCascade(Traits&& t = Traits{})
          : traits_(std::forward<Traits>(t))
        {}
 
        CommonSubExpressionCascade(const std::tuple<>, Traits&& t = Traits{})
          : traits_(std::forward<Traits>(t))
        {}
 
        template<std::size_t D = 0>
        const DepthType& get(IndexConstant<D> = IndexConstant<D>{}) const&
        {
          static_assert(D == 0, "This is the terminal cascade element, D should be 0.");
          return data_;
        }
 
        template<std::size_t D = 0>
        DepthType& get(IndexConstant<D> = IndexConstant<D>{})&
        {
          static_assert(D == 0, "This is the terminal cascade element, D should be 0.");
          return data_;
        }
 
        template<std::size_t D = 0>
        DepthType get(IndexConstant<D> = IndexConstant<D>{})&&
        {
          static_assert(D == 0, "This is the terminal cascade element, D should be 0.");
          return data_;
        }
 
        template<class... T>
        void evaluate(T&&...) {} // we don't evaluate :)
 
        constexpr static std::size_t depth()
        {
          return depth_;
        }
 
        static constexpr bool isEmpty()
        {
          return true;
        }
 
        const TraitsType& sExpTraits() const
        {
          return traits_;
        }
 
       protected:
        std::tuple<> data_; // dummy
        TraitsType traits_;
      };
 
      template<class Traits, class... SExp, class PrevSExp, class... SExpRest>
      class CommonSubExpressionCascade<Traits, std::tuple<std::tuple<SExp...>, PrevSExp, SExpRest...> >
        : public CommonSubExpressionCascade<Traits, std::tuple<PrevSExp, SExpRest...> >
      {
        using BaseType = CommonSubExpressionCascade<Traits, std::tuple<PrevSExp, SExpRest...> >;
 
        static_assert(IndexSequence<IsSubExpressionExpression<SExp>::value...>{}
                      ==
                      IndexSequence<AlwaysTrue<SExp>::value...>{},
                      "Only allowed for proper sub-expressions.");
       public:
        using DepthType = std::tuple<SExp...>;
        using DepthTupleType = std::tuple<std::tuple<SExp...>, PrevSExp, SExpRest...>;
        using typename BaseType::TraitsType;
        using BaseType::sExpTraits;
 
        static_assert(std::is_same<typename BaseType::DepthType, PrevSExp>::value,
                      "Bug, inconsistent data types.");
 
        static constexpr std::size_t depth_ = sizeof...(SExpRest) + 2;
 
        template<class T, class... SExpNode>
        CommonSubExpressionCascade(const BaseType& base, T&& t, MPL::TypeTuple<SExpNode...> sExpTuple)
          : BaseType(base)
          , data_(injectSubExpressions(std::forward<T>(t), sExpTuple, static_cast<const BaseType&>(*this)))
        {
          static_assert(sizeof...(SExpNode) == sizeof...(SExp), "Mismatching numbers of expressions.");
        }
 
        CommonSubExpressionCascade(const CommonSubExpressionCascade& other)
          : BaseType(other)
          , data_(replaceSubExpressions(const_cast<DepthType&>(other.data_), static_cast<const BaseType&>(*this)))
        {}
 
        CommonSubExpressionCascade(CommonSubExpressionCascade&& other)
          : BaseType(other)
          , data_(replaceSubExpressions(std::move(other.data_), static_cast<const BaseType&>(*this)))
        {}
 
        template<std::size_t D = 0, std::enable_if_t<(D == 0), int> = 0>
        const DepthType& get(IndexConstant<D> = IndexConstant<D>{}) const&
        {
          return data_;
        }
 
        template<std::size_t D = 0, std::enable_if_t<(D == 0), int> = 0>
        DepthType& get(IndexConstant<D> = IndexConstant<D>{}) &
        {
          return data_;
        }
 
        template<std::size_t D = 0, std::enable_if_t<(D == 0), int> = 0>
        DepthType get(IndexConstant<D> = IndexConstant<D>{}) &&
        {
          return data_;
        }
 
        template<std::size_t D, std::enable_if_t<(D > 0), int> = 0>
        const auto& get(IndexConstant<D> = IndexConstant<D>{}) const&
        {
          return BaseType::template get<D-1>();
        }
 
        template<std::size_t D, std::enable_if_t<(D > 0), int> = 0>
        auto& get(IndexConstant<D> = IndexConstant<D>{}) &
        {
          return BaseType::template get<D-1>();
        }
 
        template<std::size_t D, std::enable_if_t<(D > 0), int> = 0>
        typename BaseType::DepthType get(IndexConstant<D> = IndexConstant<D>{}) &&
        {
          return BaseType::template get<D-1>();
        }
 
        template<class SExpTraits = TraitsType>
        void evaluate(SExpTraits&& traits)
        {
          BaseType::evaluate(std::forward<SExpTraits>(traits)); // descend first
          forEach(data_, [&traits](auto&& sExp) { // then evaluate this level
              evaluateSubExpression(sExp, std::forward<SExpTraits>(traits));
            });
        }
 
        void evaluate()
        {
          evaluate(sExpTraits());
        }
 
        auto base()&&
        {
          return static_cast<BaseType&&>(*this);
        }
 
        auto& base()&
        {
          return static_cast<BaseType&>(*this);
        }
 
        const auto& base() const&
        {
          return static_cast<const BaseType&>(*this);
        }
 
        constexpr static std::size_t depth()
        {
          return depth_;
        }
 
        static constexpr bool isEmpty()
        {
          return size<DepthType>() == 0 && BaseType::isEmpt();
        }
 
       protected:
        DepthType data_;
      };
 
      template<class A, class B>
      using Unique = Expressions::AreRuntimeEqual<typename A::First, typename B::First>;
 
      template<class E, class TreePos, class... T>
      using ProcessUnique = MPL::JoinUnless<Unique, T...>;
 
      template<class T, class Traits, std::size_t D>
      struct CascadeBuildTraits;
 
      template<class T, class Traits>
      struct CascadeBuildTraits<T, Traits, 0>
      {
        using ExprType = EnclosedType<T>;
        using DepthType = MPL::TypeTuple<>;
        using SExpTuple = std::tuple<>;
        using DepthTuple = std::tuple<std::tuple<> >; // end of recursion.
        using CascadeType = CommonSubExpressionCascade<Traits, DepthTuple>;
      };
 
      template<class T, class Traits, std::size_t N>
      struct CascadeBuildTraits
      {
        using IsCandidate = IsSubExpressionCandidate<T, Traits::template IsCandidate, N>;
        using ExprType = EnclosedType<T>;
        using DepthType = Expressions::TreeExtract<
          IsCandidate::template Predicate,
          ExprType, Expressions::PackTreePair, Expressions::TreePosition<>,
          IsCandidate::template Ignore, ProcessUnique>;
        using PrevTraits = CascadeBuildTraits<T, Traits, N-1>;
        using PrevCascade = typename PrevTraits::CascadeType;
        using SExpTuple =
          std::decay_t<decltype(injectSubExpressions(std::declval<T>(), DepthType{}, std::declval<const PrevCascade&>()))>;
        static constexpr bool empty = size<SExpTuple>() == 0;
        using DepthTuple = ConditionalType<empty,
                                           typename PrevTraits::DepthTuple,
                                           AddFrontTuple<SExpTuple, typename PrevTraits::DepthTuple> >;
        using CascadeType = CommonSubExpressionCascade<Traits, DepthTuple>;
      };
 
      template<class T, class Traits, std::size_t N = Depth<T>::value,
               std::enable_if_t<(IsExpression<T>::value
                                 && !IsClosure<T>::value
                                 && N == 0
                 ), int> = 0>
      auto commonSubExpressionCascade(T&& t, Traits&& traits, IndexConstant<N> = IndexConstant<N>{})
      {
        //std::clog << __PRETTY_FUNCTION__ << std::endl;
        using BuildTraits = CascadeBuildTraits<T, Traits, N>;
        using CascadeType = typename BuildTraits::CascadeType;
        return CascadeType(std::tuple<>{}, std::forward<Traits>(traits));
      }
 
      template<class T, class Traits, std::size_t N = Depth<T>::value,
               std::enable_if_t<(IsExpression<T>::value
                                 && !IsClosure<T>::value
                                 && N > 0
                 ), int> = 0>
      auto commonSubExpressionCascade(T&& t, Traits&& traits, IndexConstant<N> = IndexConstant<N>{})
      {
        //std::clog << __PRETTY_FUNCTION__ << std::endl;
        using BuildTraits = CascadeBuildTraits<T, Traits, N>;
        if constexpr (BuildTraits::empty) {
          return Expressions::commonSubExpressionCascade(std::forward<T>(t), std::forward<Traits>(traits), IndexConstant<N-1>{});
        } else {
          using IsCandidate = typename BuildTraits::IsCandidate;
          using SExpTuple = Expressions::TreeExtract<
            IsCandidate::template Predicate,
            T, Expressions::PackTreePair, Expressions::TreePosition<>,
            IsCandidate::template Ignore, ProcessUnique>;
 
          using CascadeType = typename BuildTraits::CascadeType;
          return CascadeType(
            Expressions::commonSubExpressionCascade(std::forward<T>(t), std::forward<Traits>(traits), IndexConstant<N-1>{}),
            std::forward<T>(t), SExpTuple{}
            );
        }
      }
 
      template<class T, class Traits,
               std::enable_if_t<(IsExpression<T>::value
                                 && IsClosure<T>::value
        ), int> = 0>
      auto commonSubExpressionCascade(T&& t, Traits&& traits)
      {
        return Expressions::commonSubExpressionCascade(asExpression(std::forward<T>(t)), std::forward<Traits>(traits));
      }
 
      namespace {
 
        template<template<class T, class...> class F,
                 std::size_t N,
                 class Input,
                 class Initial,
                 class Recursive,
                 template<class...> class Unique,
                 std::enable_if_t<(N >= size<Input>()), int> = 0>
        auto extractFromCSEHelper(Input&& input,
                                  Initial&& initial,
                                  Recursive r, PredicateWrapper<Unique> u)
        {
          return std::forward<Initial>(initial);
        }
 
        template<template<class T, class...> class F,
                 std::size_t N,
                 class Input,
                 class Initial,
                 class Recursive,
                 template<class...> class Unique,
                 std::enable_if_t<(N < size<Input>()), int> = 0>
        auto extractFromCSEHelper(Input&& input,
                                  Initial&& initial,
                                  Recursive r, PredicateWrapper<Unique> u)
        {
          return extractFromCSEHelper<F, N+1>(
            std::forward<Input>(input),
            extract<F>(
              //std::forward<TupleElement<N, Input> >(get<N>(std::forward<Input>(input))),
              get<N>(std::forward<Input>(input)),
              std::forward<Initial>(initial),
              r, u
              ),
            r, u
            );
        }
      }
 
      template<template<class T, class...> class F,
               class T,
               class Initial = std::tuple<>,
               class Recursive = FalseType,
               template<class...> class Unique = AlwaysFalse,
               std::enable_if_t<IsCSECascade<T>::value && std::decay_t<T>::depth() != 0, int> = 0>
      auto extract(T&& cascade,
                   Initial&& initial = Initial{},
                   Recursive r = Recursive{},
                   PredicateWrapper<Unique> u = PredicateWrapper<Unique>{})
      {
        return extract<F>(std::forward<T>(cascade).base(),
                          extractFromCSEHelper<F, 0>(
                            std::forward<T>(cascade).get(),
                            std::forward<Initial>(initial),
                            r, u
                            ),
                          r, u);
      }
 
      template<template<class T, class...> class F,
               class T,
               class Initial = std::tuple<>,
               class Recursive = FalseType,
               template<class...> class Unique = AlwaysFalse,
               std::enable_if_t<IsCSECascade<T>::value && std::decay_t<T>::depth() == 0, int> = 0>
      auto extract(T&& cascade,
                   Initial&& initial = Initial{},
                   Recursive r = Recursive{},
                   PredicateWrapper<Unique> u = PredicateWrapper<Unique>{})
      {
        return std::forward<Initial>(initial);
      }
 
    } // NS Expressions
 
  } // ACFem
 
} // Dune
 
#endif // __DUNE_ACFEM_EXPRESSIONS_CSEOPTIMIZATION_HH__