// Copyright 2016 Carnegie Mellon University.  See LICENSE file for terms.

// Author: Michael Duggan

#ifndef _MATCHERTAGS_HPP_
#define _MATCHERTAGS_HPP_

// This file contains base tag and tag/type manipulation definitions for use by matcher.hpp.

#include <type_traits>

namespace matcher {

// A holder for types of any type
template <typename... T>
struct Types {
  Types() = delete;
};


namespace detail {
// Base class for TypedTags, so std::is_base_of() can be used.
struct TagBase {
  // Tags are for type tagging only, and are not constructable
  TagBase() = delete;
};

template <typename T>
using IsTag = std::is_base_of<TagBase, T>;

template <typename... T>
struct AreTags : std::true_type {};

template <typename S, typename... T>
struct AreTags<S, T...> :
    std::conditional<IsTag<S>::value, AreTags<T...>, std::false_type>::type {};

template <typename... T>
struct AreTags<Types<T...>> : AreTags<T...> {};

} // namespace detail


// Base of match tag types.  This type holds the following information:
//
// A) subtags, which is a list of tags that this tag has as arguments.  This is used by
//    detail::CountRef.
// B) convertible, which is a list of valid capture types for this node.  This is used by the
//    Matcher<Ref<T>> implementation.
//
template <typename RefTypes, typename... SubTags>
struct TypedTag : detail::TagBase {
  using subtags = Types<SubTags...>;
  using convertible = RefTypes;
};

// A simpler version of TypedTag for nodes that have no tag arguments
template <typename... T>
using Tag = TypedTag<Types<node_t, T...>>;


// Within this next section are operations on Types<> constructions
namespace detail {

// Determine if type S is one of the types in Rest.  If Rest is Types<...>, then it will
// determine if S is one of the types in Types<...>.  This will be either std::true_type or
// std::false_type.
template <typename S, typename... Rest>
struct HasType;

// Base case : false
template <typename S>
struct HasType<S> : std::false_type {};

// Inductive step.  true if S == T, recurse on Rest otherwise
template <typename S, typename T, typename... Rest>
struct HasType<S, T, Rest...> :
    std::conditional<std::is_same<S, T>::value,
                     std::true_type,
                     HasType<S, Rest...>>::type {};

// Convert HasType<S, Types<...>> to HasType<S, ...>
template <typename S, typename... Rest>
struct HasType<S, Types<Rest...>> : HasType<S, Rest...> {};

// _TypesInCommon determines what types are in common betwen A and B (with accumulator Acc)
template <typename A, typename B, typename Acc = Types<>>
struct _TypesInCommon;

// If A has no types, there are no types left in common.  Return the accumulator.
template <typename B, typename Acc>
struct _TypesInCommon<Types<>, B, Acc> {
  using type = Acc;
};

// If A has types, see if the first type in A is in B.  If so, add it to the accumulator and
// recurse.  Otherwise, just recurse.
template <typename T, typename... A, typename B, typename... Acc>
struct _TypesInCommon<Types<T, A...>, B, Types<Acc...>> {
  using type = typename std::conditional<
    HasType<T, B>::value,
    typename _TypesInCommon<Types<A...>, B, Types<Acc..., T>>::type,
    typename _TypesInCommon<Types<A...>, B, Types<Acc...>>::type>::type;
};

// _TypesInCommonN determines what types are in common between the Types<> argments to
// _TypesInCommonN.
template <typename... T>
struct _TypesInCommonN;

// The user-friendly version of _TypesInCommonN (doesn't require ::type)
template <typename... T>
using TypesInCommon = typename _TypesInCommonN<T...>::type;

// Base case: if only one set of types is left, return it
template <typename... T>
struct _TypesInCommonN<Types<T...>> {
  using type = Types<T...>;
};

// Inductive case: Using the types in common between A and B, recurse on T.
template <typename A, typename B, typename... T>
struct _TypesInCommonN<A, B, T...> {
  using type = TypesInCommon<typename _TypesInCommon<A, B>::type, T...>;
};

} // namespace detail

} // namespace matcher

#endif // _MATCHERTAGS_HPP_

/* Local Variables:   */
/* mode: c++          */
/* fill-column:    95 */
/* comment-column: 0  */
/* c-basic-offset: 2  */
/* End:               */