plasma.ADT willing

adt_willing.hpp

#pragma once

// Copyright plasma-effect 2015
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#include<tuple>
#include<utility>
#include<memory>
#include<type_traits>
#include<stdexcept>
#include<typeindex>

#include<boost/variant.hpp>
#include<boost/optional.hpp>

#ifdef _MSC_VER
#define PLASMA_ADT_WILLING_TEMPLATE
#else
#define PLASMA_ADT_WILLING_TEMPLATE template
#endif

namespace adt_willing
{
	namespace detail
	{
		template<class T>struct tuple_transmission
		{
			typedef std::tuple<T> type;
		};
		template<class... Ts>struct tuple_transmission<std::tuple<Ts...>>
		{
			typedef std::tuple<Ts...> type;
		};
		template<>struct tuple_transmission<void>
		{
			typedef std::tuple<> type;
		};
		template<class T>using tuple_transmission_t = typename tuple_transmission<T>::type;

		template<class... Ts>using tuple_cat_t = decltype(std::tuple_cat(std::declval<Ts>()...));

		template<class T>struct type_tag 
		{
			typedef T type;
		};
		template<int I, class T>struct id_tag 
		{
			typedef T type;
		};
		template<int I, class T>using id_tag_t = typename id_tag<I, T>::type;
		template<std::size_t Id, class... Ts>struct structure_data {};
		template<class T>struct pattern_instance_tag {};

		struct void_t {};

		template<std::size_t I, class Tuple>constexpr auto get(Tuple const& t, std::enable_if_t<(std::tuple_size<Tuple>::value > I)>* = nullptr)
		{
			return std::get<I>(t);
		}
		template<std::size_t I, class Tuple>constexpr auto get(Tuple const&, std::enable_if_t<(std::tuple_size<Tuple>::value <= I)>* = nullptr)
		{
			return void_t();
		}
		
		constexpr auto select_value(void_t, void_t)
		{
			return void_t();
		}
		template<class T>constexpr auto select_value(void_t, T const& v)->std::enable_if_t<!std::is_same<T, void_t>::value, T>
		{
			return v;
		}
		template<class T>constexpr auto select_value(T const& v, void_t)->std::enable_if_t<!std::is_same<T, void_t>::value, T>
		{
			return v;
		}
		template<class T, class U>constexpr auto select_value(T const&, U const&)
		{
			static_assert(std::is_same<T, void_t>::value || std::is_same<U, void_t>::value, "pattern_match conflict");
			return 0;
		}

		template<class IndexSequence>struct tuple_merge_i;
		template<std::size_t... Is>struct tuple_merge_i<std::index_sequence<Is...>>
		{
			template<class T, class U>static constexpr auto run(T const& t, U const& u)
			{
				return std::make_tuple(select_value(detail::get<Is>(t), detail::get<Is>(u))...);
			}
		};
		template<class T, class U>constexpr auto tuple_merge(T const& t, U const& u)
		{
			return tuple_merge_i<std::make_index_sequence<std::max(std::tuple_size<T>::value, std::tuple_size<U>::value)>>::run(t, u);
		}
		template<class T>auto optional_merge(boost::none_t, boost::optional<T>const&)
		{
			return boost::none;
		}
		template<class U>auto optional_merge(boost::optional<U>const&, boost::none_t)
		{
			return boost::none;
		}
		template<class T, class U>auto optional_merge(boost::optional<T>const& t, boost::optional<U>const& u)
		{
			if(t&&u)
				return boost::make_optional(tuple_merge(*t, *u));
			return static_cast<decltype(boost::make_optional(tuple_merge(*t, *u)))>(boost::none);
		}
		template<class T, class... Ts>auto optional_merge(T const& t, Ts const&... ts)
		{
			return optional_merge(t, optional_merge(ts...));
		}

		template<class IndexSequence>struct make_one_tuple_i;
		template<std::size_t... Is>struct make_one_tuple_i<std::index_sequence<Is...>>
		{
			template<class T>static constexpr auto run(T const& v)
			{
				return std::make_tuple(id_tag_t<Is, void_t>()..., v);
			}
		};
		template<std::size_t I, class T>constexpr auto make_one_tuple(T const& v)
		{
			return make_one_tuple_i<std::make_index_sequence<I>>::run(v);
		}

		template<class... Ts>struct true_optional;
		template<class... Ts>struct true_optional<boost::none_t, Ts...> :true_optional<Ts...> {};
		template<class T, class... Ts>struct true_optional<T, Ts...>
		{
			typedef T type;
		};
		template<>struct true_optional<>
		{
			typedef boost::none_t type;
		};
		template<class... Ts>using true_optional_t = typename true_optional<Ts...>::type;
		
		template<class IndexSequence>struct tuple_call_i;
		template<std::size_t... Is>struct tuple_call_i<std::index_sequence<Is...>>
		{
			template<class Tuple, class Func>static auto run(Func const& func, Tuple const& t)
			{
				return func(std::get<Is>(t)...);
			}
		};
		
		template<class Tuple, class Func>auto tuple_call(Func func, Tuple const& t)
		{
			return tuple_call_i<std::make_index_sequence<std::tuple_size<Tuple>::value>>::run(func, t);
		}

		struct pattern_tag {};
	}

	namespace place_holder
	{
		template<int V, int I, int... Is>struct value_t :value_t<10 * V + I, Is...> {};
		template<int V, int I>struct value_t<V, I> :std::integral_constant<int, 10 * V + I> {};
		template<int Id>struct place_holder_t :detail::pattern_tag 
		{
			template<class Func>struct pattern_match_t
			{
				Func func;
				template<class ReturnType, class T, class... Ts>auto normal_call(detail::type_tag<ReturnType>, T const& v, Ts const&... args)const
				{
					auto d = v.get_data(place_holder_t<0>());
					if (d)
					{
						return boost::make_optional(detail::tuple_call(func, std::tuple_cat(*d, std::make_tuple(std::cref(args)...))));
					}
					return static_cast<decltype(boost::make_optional(detail::tuple_call(func, std::tuple_cat(*d, std::make_tuple(std::cref(args)...)))))>(boost::none);
				}
				template<class ReturnType,class T, class Recursion, class... Ts>auto recursion_call(detail::type_tag<ReturnType>, Recursion recur, T const& v, Ts const&... args)const
				{
					auto d = v.get_data(place_holder_t<0>());
					if (d)
					{
						return boost::make_optional(detail::tuple_call(func, std::tuple_cat(std::make_tuple(recur), *d, std::make_tuple(std::cref(args)...))));
					}
					return static_cast<decltype(boost::make_optional(detail::tuple_call(func, std::tuple_cat(std::make_tuple(recur), *d, std::make_tuple(std::cref(args)...)))))>(boost::none);
				}
			};
			template<class Func>auto operator<=(Func const& func)const
			{
				return pattern_match_t<Func>{func};
			}
		};
		template<char... Cs>constexpr auto operator"" _()
		{
			return place_holder_t<value_t<0, (Cs - '0')...>::value>();
		}
	}
	template<class T>struct get_structure
	{
		typedef typename T::structure type;
	};
	template<int I>struct get_structure<place_holder::place_holder_t<I>>
	{
		typedef place_holder::place_holder_t<I> type;
	};
	template<int I>struct get_structure<place_holder::place_holder_t<I> const&>
	{
		typedef place_holder::place_holder_t<I> type;
	};


	template<class T>using get_structure_t = typename get_structure<T>::type;
	struct recursion_tag {};

	template<class... Types>struct data_type
	{
		typedef data_type<Types...> this_type;
		typedef std::tuple<detail::tuple_transmission_t<Types>...> template_parameter;
		template<std::size_t Id>using parameter_t = std::tuple_element_t<Id, template_parameter>;
		template<class IndexSequence>struct container_t;
		typedef container_t<std::make_index_sequence<sizeof...(Types)>> container;
		typedef std::shared_ptr<container> ptr_type;
		ptr_type ptr_;

		template<class T, class = void>struct value_data
		{
			typedef T value_type;
			T value_;

			value_data(value_type const& v) :value_(v) {}
			value_data(value_data const&) = default;
			value_data(value_data&&) = default;
			value_data& operator=(value_data const&) = default;
			value_data& operator=(value_data&&) = default;
			~value_data() = default;

			operator value_type const&()const
			{
				return value_;
			}

			bool operator==(value_data<T>const& rhs)const
			{
				return value_ == rhs.value_;
			}

			template<int I>auto get_data(place_holder::place_holder_t<I>)const
			{
				return boost::make_optional(detail::make_one_tuple<I>(value_));
			}
		};
		template<class T>struct value_data<T, std::enable_if_t<std::is_same<T, recursion_tag>::value>>
		{
			typedef this_type value_type;
			ptr_type value_;

			value_data(value_type const& v) :value_(v.ptr_) {}
			value_data(value_data const&) = default;
			value_data(value_data&&) = default;
			value_data& operator=(value_data const&) = default;
			value_data& operator=(value_data&&) = default;
			~value_data() = default;

			operator value_type const&()const
			{
				return this_type(value_);
			}

			bool operator==(value_data<T>const& rhs)const
			{
				return *value_ == *(rhs.value_);
			}

			template<class Structure>auto get_data(Structure)const
			{
				return this_type(value_).get_data(Structure());
			}
		};
		template<class T>using value_type = typename value_data<T>::value_type;

		template<std::size_t Id, class Tuple>struct inside_data;
		template<std::size_t Id, class... Ts>struct inside_data<Id, std::tuple<Ts...>>
		{
			std::tuple<value_data<Ts>...> value_;

			inside_data(value_type<Ts>const&... args) :value_(args...) {}
			inside_data(inside_data const&) = default;
			inside_data(inside_data&&) = default;
			inside_data& operator=(inside_data const&) = default;
			inside_data& operator=(inside_data&&) = default;
			~inside_data() = default;

			bool operator==(inside_data<Id, std::tuple<Ts...>>const& rhs)const
			{
				return value_ == rhs.value_;
			}

			template<class IndexSequence>struct get_data_i;
			template<std::size_t... Is>struct get_data_i<std::index_sequence<Is...>>
			{
				template<class T, std::size_t I>static auto run(T const&, detail::structure_data<I>)
				{
					return boost::make_optional(std::tuple<>());
				}
				template<class T, std::size_t I, class... Us>static auto run(T const& t, detail::structure_data<I, Us...>, std::enable_if_t<sizeof...(Us) != 0>* = nullptr)
				{
					return detail::optional_merge(std::get<Is>(t).get_data(Us())...);
				}
				
			};
			template<std::size_t I, class... Us>auto get_data(detail::structure_data<I, Us...>, std::enable_if_t<(static_cast<std::size_t>(I) == Id) && (sizeof...(Ts) == sizeof...(Us))>* = nullptr)const
			{
				return get_data_i<std::make_index_sequence<sizeof...(Us)>>::run(value_, detail::structure_data<I, Us...>());
			}
			template<std::size_t I, class... Us>auto get_data(detail::structure_data<I, Us...>, std::enable_if_t<(static_cast<std::size_t>(I) != Id) || (sizeof...(Ts) != sizeof...(Us))>* = nullptr)const
			{
				return boost::none;
			}

		};
		template<std::size_t Id>using inside_data_t = inside_data<Id, parameter_t<Id>>;
		template<std::size_t... Is>struct container_t<std::index_sequence<Is...>>
		{
			boost::variant<inside_data_t<Is>...> value_;

			template<std::size_t Id>container_t(inside_data_t<Id> v) :value_(v) {}
			container_t(container_t const&) = default;
			container_t(container_t&&) = default;
			container_t& operator=(container_t const&) = default;
			container_t& operator=(container_t&&) = default;
			~container_t() = default;

			bool operator==(container_t<std::index_sequence<Is...>>const& rhs)const
			{
				return value_ == rhs.value_;
			}
			template<class Structure>auto get_data(Structure)const
			{
				typedef detail::true_optional_t<decltype(std::declval<inside_data_t<Is>>().PLASMA_ADT_WILLING_TEMPLATE get_data(std::declval<Structure>()))...> return_type;
				return boost::apply_visitor([](auto const& v) {return static_cast<return_type>(v.PLASMA_ADT_WILLING_TEMPLATE get_data(Structure()));}, value_);
			}
		};
		bool operator==(this_type const& rhs)const
		{
			return *ptr_ == *rhs.ptr_;
		}
		template<int I>auto get_data(place_holder::place_holder_t<I>)const
		{
			return boost::make_optional(detail::make_one_tuple<I>(*this));
		}
		template<class Structure>auto get_data(Structure)const
		{
			return ptr_->get_data(Structure());
		}
		

		template<class T>struct instance_t;
		template<std::size_t Id, class... Ts>struct instance_t<inside_data<Id, std::tuple<Ts...>>> :detail::pattern_tag
		{
			this_type operator()(value_type<Ts>const&... args)const
			{
				return this_type(std::make_shared<container>(inside_data_t<Id>(args...)));
			}
			typedef detail::structure_data<Id> structure;

			template<class... Us>struct pattern_t :detail::pattern_tag
			{
				typedef detail::structure_data<Id, get_structure_t<Us>...> structure;

				template<class Func>struct pattern_match_t
				{
					Func func;
					template<class ReturnType, class... Cs>auto normal_call(detail::type_tag<ReturnType>, this_type const& v, Cs const&... args)const
					{
						auto d = v.get_data(structure());
						if (d)
						{
							return boost::make_optional(detail::tuple_call(func, std::tuple_cat(*d, std::make_tuple(std::cref(args)...))));
						}
						return static_cast<decltype(boost::make_optional(detail::tuple_call(func, std::tuple_cat(*d, std::make_tuple(std::cref(args)...)))))>(boost::none);
					}
					template<class ReturnType, class Recursion, class... Cs>auto recursion_call(detail::type_tag<ReturnType>, Recursion recur, this_type const& v, Cs const&... args)const
					{
						auto d = v.get_data(structure());
						if (d)
						{
							return boost::make_optional(detail::tuple_call(func, std::tuple_cat(std::make_tuple(recur), *d, std::make_tuple(std::cref(args)...))));
						}
						return static_cast<decltype(boost::make_optional(detail::tuple_call(func, std::tuple_cat(std::make_tuple(recur), *d, std::make_tuple(std::cref(args)...)))))>(boost::none);
					}
				};

				template<class Func>auto operator<=(Func func)const
				{
					return pattern_match_t<Func>{func};
				}
			};

			template<class U, class... Us>std::enable_if_t<std::is_base_of<detail::pattern_tag,U>::value, pattern_t<U, Us...>> operator()(U const&, Us const&...)const
			{
				return pattern_t<U, Us...>();
			}
			template<class Func>struct pattern_match_t
			{
				Func func;
				template<class ReturnType, class... Cs>auto normal_call(detail::type_tag<ReturnType>, this_type const& v, Cs const&... args)const
				{
					if (v.ptr_->value_.which() == Id)
					{
						return boost::make_optional(detail::tuple_call(func, std::make_tuple(std::cref(args)...)));
					}
					return static_cast<decltype(boost::make_optional(detail::tuple_call(func, std::make_tuple(std::cref(args)...))))>(boost::none);
				}
				template<class ReturnType, class Recursion, class... Cs>auto recursion_call(detail::type_tag<ReturnType>, Recursion recur, this_type const& v, Cs const&... args)const
				{
					if (v.ptr_->value_.which() == Id)
					{
						return boost::make_optional(detail::tuple_call(func, std::tuple_cat(std::make_tuple(recur), std::make_tuple(std::cref(args)...))));
					}
					return static_cast<decltype(boost::make_optional(detail::tuple_call(func, std::tuple_cat(std::make_tuple(recur), std::make_tuple(std::cref(args)...)))))>(boost::none);
				}
			};
			template<class Func>auto operator<=(Func const& func)const
			{
				return pattern_match_t<Func>{func};
			}
		};
		
		template<std::size_t Id>static auto get_instance_function()
		{
			return instance_t<inside_data_t<Id>>();
		}

		data_type(ptr_type const& ptr) :ptr_(ptr) {}
		data_type(data_type const&) = default;
		data_type(data_type&&) = default;
		data_type& operator=(data_type const&) = default;
		data_type& operator=(data_type&&) = default;
		~data_type() = default;
	};

	class no_hit_exception :public std::logic_error
	{
	public:
		std::type_index index;
		no_hit_exception(std::type_index in) :std::logic_error("pattern match error"), index(in) {}
	};

	template<class ReturnType>struct make_pattern_match_t
	{
		template<class... PatternInstances>struct pattern_match_instance_t
		{
			std::tuple<PatternInstances...> pis;
			template<std::size_t I, class T, class... Ts>std::enable_if_t<(I + 1 != sizeof...(PatternInstances)), ReturnType> run(T const& data, Ts const&...args)const
			{
				if (auto d = std::get<I>(pis).normal_call(detail::type_tag<ReturnType>(), data, args...))
				{
					return *d;
				}
				return run<I + 1>(data, args...);
			}
			template<std::size_t I, class T, class... Ts>std::enable_if_t<(I + 1 == sizeof...(PatternInstances)), ReturnType> run(T const& data, Ts const&...args)const
			{
				if (auto d = std::get<I>(pis).normal_call(detail::type_tag<ReturnType>(), data, args...))
				{
					return *d;
				}
				throw no_hit_exception(typeid(*this));
			}

			template<class T, class... Ts>ReturnType operator()(T const& data, Ts const&... args)const
			{
				return run<0>(data, args...);
			}
			template<class Instance>auto operator|(Instance const& instance)const
			{
				return pattern_match_instance_t<PatternInstances..., Instance>{std::tuple_cat(pis, std::make_tuple(instance))};
			}
		};
		template<class Instance>auto operator|(Instance const& instance)const
		{
			return pattern_match_instance_t<Instance>{std::make_tuple(instance)};
		}
	};
	template<class ReturnType>auto pattern_match()
	{
		return make_pattern_match_t<ReturnType>();
	}

	template<class ReturnType>struct make_recursion_match_t
	{
		template<class... PatternInstances>struct pattern_match_instance_t
		{
			std::tuple<PatternInstances...> pis;
			template<std::size_t I, class T, class... Ts>std::enable_if_t<(I + 1 != sizeof...(PatternInstances)), ReturnType> run(T const& data, Ts const&...args)const
			{
				if (auto d = std::get<I>(pis).recursion_call(detail::type_tag<ReturnType>(),std::cref(*this), data, args...))
				{
					return *d;
				}
				return run<I + 1>(data, args...);
			}
			template<std::size_t I, class T, class... Ts>std::enable_if_t<(I + 1 == sizeof...(PatternInstances)), ReturnType> run(T const& data, Ts const&...args)const
			{
				if (auto d = std::get<I>(pis).recursion_call(detail::type_tag<ReturnType>(), std::cref(*this), data, args...))
				{
					return *d;
				}
				throw no_hit_exception(typeid(*this));
			}

			template<class T, class... Ts>ReturnType operator()(T const& data, Ts const&... args)const
			{
				return run<0>(data, args...);
			}
			template<class Instance>auto operator|(Instance const& instance)const
			{
				return pattern_match_instance_t<PatternInstances..., Instance>{std::tuple_cat(pis, std::make_tuple(instance))};
			}
		};
		template<class Instance>auto operator|(Instance const& instance)const
		{
			return pattern_match_instance_t<Instance>{std::make_tuple(instance)};
		}
	};
	template<class ReturnType>auto recursion_match()
	{
		return make_recursion_match_t<ReturnType>();
	}
}

main.cpp

#include"adt_willing.hpp"
#include<iostream>

using namespace adt_willing;
using namespace place_holder;
typedef data_type<void, std::tuple<int, recursion_tag>> type;
const auto Nil = type::get_instance_function<0>();
const auto Tree = type::get_instance_function<1>();

int main()
{
	const auto func = recursion_match<int>()
		| Tree(0_, Tree(1_, 2_)) <= [](auto f, int x, int y, type t) {return x + y + f(t);}
		| Tree(0_, Nil) <= [](auto, int x) {return x;}
		| Nil <= [](auto) {return 0;};;
	std::cout << func(Tree(1, Tree(2, Nil()))) << std::endl;
	std::cout << func(Tree(1, Nil())) << std::endl;
}

reference.md

##なにこれ 次世代の代数的データ型！plasma.ADTここに極めり！

##極まってないだろ はい。

##使い方 main.cppを読めばわかる。

##注意 今回メモ化バージョンを搭載しておりません。