derived-term.hh

Go to the documentation of this file.

#pragma once

#include <vcsn/algos/constant-term.hh>
#include <vcsn/algos/derivation.hh>
#include <vcsn/algos/split.hh>
#include <vcsn/algos/to-expansion.hh>
#include <vcsn/core/automaton.hh> // all_out
#include <vcsn/core/expression-automaton.hh>
#include <vcsn/core/mutable-automaton.hh>
#include <vcsn/ctx/fwd.hh>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/value.hh>
#include <vcsn/misc/getargs.hh>
#include <vcsn/misc/raise.hh>
#include <vcsn/weightset/polynomialset.hh>

namespace vcsn
{
  namespace detail
  {
    struct derived_term_algo
    {
      enum algo_t
        {
          derivation,
          expansion,
        };

      derived_term_algo(algo_t a, bool b, bool d)
        : algo(a)
        , breaking(b)
        , determinize(d)
      {}

      derived_term_algo(std::string algo)
      {
        using dta = derived_term_algo;
        static const auto map = getarg<derived_term_algo>
          {
            "derived-term algorithm",
            {
              //                          { algo, breaking, deterministic }.
              {"auto",                    dta{expansion,  false, false}},
              {"breaking_derivation",     "derivation,breaking"},
              {"breaking_expansion",      "expansion,breaking"},
              {"derivation",              dta{derivation, false, false}},
              {"derivation,breaking",     dta{derivation, true,  false}},
              {"derivation,deterministic",dta{derivation, false,  true}},
              {"derivation_breaking",     "derivation,breaking"},
              {"expansion",               dta{expansion,  false, false}},
              {"expansion,breaking",      dta{expansion,  true,  false}},
              {"expansion,deterministic", dta{expansion,  false, true}},
              {"expansion_breaking",      "expansion,breaking"},
            }
          };
        if (boost::starts_with(algo, "lazy,"))
          algo = algo.substr(5);
        *this = map[algo];
      }

      algo_t algo;
      bool breaking = false;
      bool determinize = false;
    };

    /*--------------------------.
    | derived_term_automaton.   |
    `--------------------------*/

    template <typename ExpSet,
              bool = labelset_t_of<ExpSet>::is_letterized()>
    struct derived_term_automaton_members
    {
      derived_term_automaton_members(const ExpSet& rs)
        : gens{rs.labelset()->generators()}
      {}

      using ls_t = labelset_t_of<ExpSet>;
      using genset_t = decltype(std::declval<ls_t>().generators());
      genset_t gens;
    };

    template <typename ExpSet>
    struct derived_term_automaton_members<ExpSet, false>
    {
      derived_term_automaton_members(const ExpSet&){}
    };

    template <typename ExpSet>
    class derived_term_automaton_impl
      : public automaton_decorator<expression_automaton<mutable_automaton<context_t_of<ExpSet>>>>
    {
    public:
      using expressionset_t = ExpSet;
      using expression_t = typename expressionset_t::value_t;

      using context_t = context_t_of<expressionset_t>;
      using weightset_t = weightset_t_of<context_t>;

      using automaton_t = expression_automaton<mutable_automaton<context_t>>;
      using state_t = state_t_of<automaton_t>;

      using self_t = derived_term_automaton_impl;
      using super_t = automaton_decorator<automaton_t>;

      static symbol sname()
      {
        static auto res = symbol{"derived_term_automaton<"
                                 + expressionset_t::sname()
                                 + ">"};
        return res;
      }

      std::ostream& print_set(std::ostream& o, format fmt = {}) const
      {
        o << "derived_term_automaton<";
        return rs_.print_set(o, fmt) << '>';
      }

      derived_term_automaton_impl(const expressionset_t& rs,
                                  derived_term_algo algo)
        : super_t{make_shared_ptr<automaton_t>(rs)}
        , rs_{rs}
        , algo_{algo}
        , members_{rs}
      {}

      automaton_t operator()(const expression_t& exp)
      {
        try
          {
            if (algo_.algo == derived_term_algo::derivation)
              return via_derivation(exp);
            else
              return via_expansion(exp);
          }
        catch (const std::runtime_error& e)
          {
            raise(e, "  while computing derived-term of: ", to_string(rs_, exp));
          }
      }

      automaton_t via_derivation(const expression_t& exp)
      {
        init_(exp);
        while (!aut_->todo_.empty())
          {
            auto p = std::move(aut_->todo_.top());
            aut_->todo_.pop();
            complete_via_derivation_(p.first, p.second);
          }
        return aut_;
      }

      automaton_t via_expansion(const expression_t& exp)
      {
        init_(exp);
        while (!aut_->todo_.empty())
          {
            auto p = std::move(aut_->todo_.top());
            aut_->todo_.pop();
            complete_via_expansion_(p.first, p.second);
          }
        return aut_;
      }

      //    private:
      using super_t::aut_;

      void init_(const expression_t& exp)
      {
        if (algo_.breaking)
          for (const auto& p: split(rs_, exp))
            aut_->set_initial(label_of(p), weight_of(p));
        else
          aut_->set_initial(exp, ws_.one());
      }

      void complete_(state_t s) const
      {
        const auto& orig = aut_->origins();
        auto sn = orig.at(s);
        const_cast<self_t&>(*this).complete_via_expansion_(s, sn);
      }

      auto all_out(state_t s) const
        -> decltype(vcsn::detail::all_out(aut_, s))
      {
        if (this->is_lazy(s))
          complete_(s);
        return vcsn::detail::all_out(aut_, s);
      }

      template <typename ES = expressionset_t,
                typename = std::enable_if<labelset_t_of<ES>::is_letterized()>>
      void complete_via_derivation_(state_t s, const expression_t& src)
      {
        aut_->set_lazy(s, false);
        aut_->set_final(s, constant_term(rs_, src));
        for (auto l : members_.gens)
          {
            auto p = derivation(rs_, src, l, algo_.breaking);
            if (algo_.determinize)
              {
                auto m = ps_.determinize(p);
                aut_->new_transition(s, label_of(m), l, weight_of(m));
              }
            else
              for (const auto& m: p)
                aut_->new_transition(s, label_of(m), l, weight_of(m));
          }
      }

      void complete_via_expansion_(state_t s, const expression_t& src)
      {
        aut_->set_lazy(s, false);
        auto expansion = to_expansion_(src);
        if (algo_.determinize)
          expansion = es_.determinize(expansion);

        aut_->set_final(s, expansion.constant);
        for (const auto& p: expansion.polynomials)
          if (algo_.breaking)
            for (const auto& m1: p.second)
              for (const auto& m2: split(rs_, label_of(m1)))
                aut_->new_transition(s, label_of(m2), p.first,
                                     ws_.mul(weight_of(m1), weight_of(m2)));
          else if (algo_.determinize)
            {
              auto m = ps_.determinize(p.second);
              aut_->new_transition(s, label_of(m), p.first, weight_of(m));
            }
          else
            for (const auto& m: p.second)
              aut_->new_transition(s, label_of(m), p.first, weight_of(m));
      }

      expressionset_t rs_;
      weightset_t ws_ = *rs_.weightset();
      using polynomialset_t = rat::expression_polynomialset_t<expressionset_t>;
      polynomialset_t ps_ = make_expression_polynomialset(rs_);
      derived_term_algo algo_;

      using expansionset_t = rat::expansionset<expressionset_t>;
      expansionset_t es_ = {rs_};
      using to_expansion_t = rat::to_expansion_visitor<expressionset_t>;
      to_expansion_t to_expansion_ = {rs_};
      derived_term_automaton_members<expressionset_t> members_ = {rs_};
    };
  }

  template <typename ExpSet>
  using derived_term_automaton
    = std::shared_ptr<detail::derived_term_automaton_impl<ExpSet>>;

  template <typename ExpSet>
  auto
  make_derived_term_automaton(const ExpSet& rs,
                              const detail::derived_term_algo& algo)
    -> derived_term_automaton<ExpSet>
  {
    using res_t = derived_term_automaton<ExpSet>;
    return make_shared_ptr<res_t>(rs, algo);
  }

  template <typename ExpSet>
  std::enable_if_t<labelset_t_of<ExpSet>::is_letterized(),
    expression_automaton<mutable_automaton<typename ExpSet::context_t>>>
  derived_term(const ExpSet& rs,
               const typename ExpSet::value_t& r,
               const std::string& algo = "auto")
  {
    auto a = detail::derived_term_algo(algo);
    auto dt = make_derived_term_automaton(rs, a);
    return dt->operator()(r);
  }

  template <typename ExpSet>
  std::enable_if_t<!labelset_t_of<ExpSet>::is_letterized(),
    expression_automaton<mutable_automaton<typename ExpSet::context_t>>>
  derived_term(const ExpSet& rs,
               const typename ExpSet::value_t& r,
               const std::string& algo = "auto")
  {
    auto a = detail::derived_term_algo(algo);
    require(a.algo == detail::derived_term_algo::expansion,
            "derived_term: cannot use derivation on non-letterized labelsets");
    // Do not call the operator(), this would trigger the compilation
    // of via_derivation, which does not compile (on purpose) for non
    // letterized labelsets.
    auto dt = make_derived_term_automaton(rs, a);
    return dt->via_expansion(r);
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename ExpSet, typename String>
      automaton derived_term(const expression& exp, const std::string& algo)
      {
        const auto& e = exp->as<ExpSet>();
        const auto& rs = e.valueset();
        const auto& r = e.value();
        if (boost::starts_with(algo, "lazy,"))
          {
            auto a = vcsn::detail::derived_term_algo(algo);
            require(a.algo == vcsn::detail::derived_term_algo::expansion,
                    "derived_term: laziness works only with expansions");
            // Do not call the operator(), this would trigger the compilation
            // of via_derivation, which does not compile (on purpose) for non
            // letterized labelsets.
            auto res = make_derived_term_automaton(rs, a);
            res->init_(r);
            return res;
          }
        else
          return ::vcsn::derived_term(rs, r, algo);
      }
    }
  }
} // vcsn::