term_utils.hh

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef __TERM_UTILS_HH
# define __TERM_UTILS_HH

# include <functional>
# include <strategies/failure.hh>
# include <max_shared/max_shared_ptr.hh>
# include "hash/tuple_hash.hh"
# include "type_traits/overloading_priority.hh"
# include "term_concept.hh"

namespace aurelia {

  template <typename Constructor, typename... SubPatterns>
  struct pattern;

  template <typename Term, typename Constr>
  struct get_tuple {
  };

  template <typename Strat, typename tuple, size_t N, size_t size>
  struct tuple_all {
    static void apply(const Strat& s, tuple& t) {
      std::get<N>(t) = s(std::get<N>(t));
      tuple_all<Strat, tuple, N+1, size>::apply(s, t);
    }
  };

  template <typename Strat, typename tuple, size_t size>
  struct tuple_all<Strat, tuple, size, size> {
    static void apply(const Strat&, tuple&) {
    }
  };

  template <typename Term, typename Constr>
  struct virtual_term_constr {
    typedef typename get_tuple<Term,Constr>::tuple tuple;

    virtual const tuple&
    getvalues(const Constr&) const throw (failure) {
      throw failure();
    }

    virtual Term build(tuple&&) const {
      throw failure();
    }

    template <typename Strat>
    Term all_prim(const Strat& s) const {
      tuple out(getvalues(Constr()));
      tuple_all<Strat, tuple, 0, std::tuple_size<tuple>::value>
        ::apply(s, out);
      return build(std::move(out));
    }
  };

  template <typename T, typename... Tail>
  struct pos_of;

  template <typename T, typename Head, typename... Tail>
  struct pos_of<T, Head, Tail...> {
    enum: size_t { value = (size_t)pos_of<T, Tail...>::value+1 };
  };

  template <typename T, typename... Tail>
  struct pos_of<T, T, Tail...> {
    enum: size_t { value = 0 };
  };

  template <typename Term, typename VirtualTerm, typename Strat,
            typename... Constrs>
  struct dispatch_all {
    static Term apply(const Strat&, size_t, const VirtualTerm&) {
      throw failure();
    }
  };

  template <typename Term, typename VirtualTerm, typename Strat,
            typename Constr, typename... Constrs>
  struct dispatch_all<Term, VirtualTerm, Strat, Constr, Constrs...> {
    static Term apply(const Strat& s, size_t n, const VirtualTerm& v) {
      if (n == 0)
        return static_cast<const virtual_term_constr<Term, Constr>*>(&v)
          ->all_prim(s);
      return dispatch_all<Term, VirtualTerm, Strat, Constrs...>
	::apply(s, n-1, v);
    }
  };

  template <typename Term, typename... Constr>
  struct virtual_term: public virtual_term_constr<Term, Constr>... {
    virtual size_t constr() const = 0;

    template <typename C, typename ...V>
    void match(pattern<C, V...>& p) const throw (failure) {
      p.subpatterns =
        ((const virtual_term_constr<Term,C>*)this)->getvalues(p.constructor);
    }

    template <typename Strat>
    Term all_prim(const Strat& s) const {
      return dispatch_all<Term, virtual_term, Strat, Constr...>
	::apply(s, constr(), *this);
    }

    virtual bool operator==(const virtual_term& other) const = 0;
    virtual bool operator!=(const virtual_term& other) const = 0;

    virtual size_t hash() const = 0;
  };

  template <typename Constr, typename Term>
  struct ConstrNb {
  };

  template <typename Constr, typename Term, typename... Constrs>
  struct ConstrNb<Constr, virtual_term<Term, Constrs...> > {
    enum: size_t { value = (size_t)pos_of<Constr, Constrs...>::value };
  };

  template <typename Type, typename Constr>
  struct build_type {};

  template <typename Real, typename... Constrs>
  struct term {
    typedef virtual_term<Real, Constrs...> virt;
    std::shared_ptr<virt> l;

    term(virt *ptr): l(ptr) {}

    term(const term&) = default;

    term(term&& other): l(std::move(other.l)) {
    }

    term(): l((virt*)NULL) {}

    Real& operator=(term&& other) {
      std::swap(l, other.l);
      return *static_cast<Real*>(this);
    }

    Real& operator=(const term& other) {
      if (&other == this)
        return *static_cast<Real*>(this);
      return *this = term(other);
    }

    template <typename Constr, typename ...V>
    void match(pattern<Constr, V...>& p) const throw (failure) {
      l->match(p);
    }

    bool operator==(const term& other) const {
      return *l == *(other.l);
    }

    bool operator!=(const term& other) const {
      return *l != *(other.l);
    }

    size_t hash() const {
      if (l.get() == (virt*)NULL)
        return 0;
      return l->hash();
    }

    template <typename Strat>
    term all_prim(const Strat& s) const {
      return l->all_prim(s);
    }
  };

  template <typename Strat, typename T, typename... Constrs>
  term<T, Constrs...> all_primitive(const Strat& s,
                                    const term<T, Constrs...>& term) {
    return term.all_prim(s);
  }

  template <typename Real, typename... Constrs>
  struct term_model<term<Real, Constrs...> > {
    struct model {
      typedef term<Real, Constrs...> type;
    };
  };

  template <typename Real, typename Constr, typename Super>
  struct std_term: public Super::virt {
    enum { constrnb = (size_t)ConstrNb<Constr, typename Super::virt>::value };

    typedef typename get_tuple<Super, Constr>::tuple tuple;
    struct core_type {
      tuple args;
      size_t hash() const {
        return std::hash<tuple>()(args);
      };

      core_type() = default;
      core_type(tuple&& args): args(std::move(args)) {}
      core_type(core_type&& other): args(std::move(other.args)) {
      }

      bool operator==(const core_type& other) const {
        return args == other.args;
      }

      bool operator!=(const core_type& other) const {
        return args != other.args;
      }
    };
    max_shared_ptr<core_type> core;

    virtual size_t constr() const {
      return constrnb;
    }

    virtual Super build(tuple&& t) const {
      return std_term(std::move(t));
    }

    virtual size_t hash() const {
      return core->hash();
    }

    operator Super() const {
      return Super((typename Super::virt*)new std_term(*this));
    }

    std_term(const tuple& args): core(args) {}
    std_term(tuple&& args): core(std::move(args)) {}

    std_term(const std_term& other): core(other.core) {}
    std_term(std_term&& other): core(std::move(other.core)) {}

    virtual const tuple& getvalues(const Constr&) const throw() {
      return (*core).args;
    }

    virtual bool operator==(const typename Super::virt& other) const {
      const std_term* ro = dynamic_cast<const std_term*>(&other);
      if (ro == NULL)
        return false;
      return core == ro->core;
    }

    virtual bool operator!=(const typename Super::virt& other) const {
      const std_term* ro = dynamic_cast<const std_term*>(&other);
      if (ro == NULL)
        return true;
      return core != ro->core;
    }
  };

  template <typename T, typename Constr, size_t N,
            typename tuple, typename... SubPatterns>
  struct build_real_type;

  template <typename T, typename Constr, size_t N,
            typename tuple, typename Head, typename... SubPatterns>
  struct build_real_type<T,
                         Constr, N, tuple, Head, SubPatterns...> {
    template <typename... Args>
    static T
    build(const tuple& t, Args... args) {
      static_assert((N+sizeof...(SubPatterns)+1) ==
                    std::tuple_size<tuple>::value,
                    "Was not the right number of arguments");
      static_assert(N == sizeof...(Args),
                    "Was not the right number of arguments");
      return build_real_type<T, Constr, N+1, tuple, SubPatterns...>
        ::build(t, std::forward<Args>(args)..., *std::get<N>(t));
    }
  };

  template <typename T,
            typename Constr, size_t N, typename tuple>
  struct build_real_type<T, Constr, N, tuple> {
    template <typename... Args>
    static T
    build(const tuple&, Args... args) {
      static_assert(N == std::tuple_size<tuple>::value,
                    "Was not the right number of arguments");
      static_assert(N == sizeof...(Args),
                    "Was not the right number of arguments");
      return T(new typename build_type<T, Constr>::
               type(std::forward<Args>(args)...));
    }
  };

}

#endif