///////////////////////////////////////////////////////////////////////////////
//  Copyright 2006 Eric Niebler. Distributed under the Boost
//  Software License, Version 1.0. (See accompanying file
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#include <cctype>
#include <iostream>
#include <boost/assert.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/spirit/fusion/sequence/get.hpp>
#include <boost/xpressive/proto/proto.hpp>
#include <boost/xpressive/proto/compiler/fold.hpp>
#include <boost/xpressive/proto/compiler/pass_through.hpp>

namespace boost
{
    // global tags
    struct char_tag {};
    struct ichar_tag {};
    struct istring_tag {};
    struct ichar_range_tag {};

    // global primitives
    proto::unary_op<char_tag, proto::noop_tag> const char_;

    // literal, for storing and naming proto-ified constants.
    template<typename T>
    struct literal
      : proto::unary_op<T, proto::noop_tag>
    {
        literal(T const &t)
          : proto::unary_op<T, proto::noop_tag>(t)
        {
        }

        template<typename U>
        literal(literal<U> const &that)
          : proto::unary_op<T, proto::noop_tag>(that.arg)
        {
        }
    };

    // lit(), for creating proto literals
    template<typename T>
    literal<T> lit(T const &t)
    {
        return literal<T>(t);
    }
}

namespace boost { namespace spirit2
{

    // Spirit2-specific tags ...
    struct parser_tag {};
    struct no_case_tag {};

    // handy typedefs
    typedef proto::unary_op<char_tag, proto::noop_tag> anychar_p;
    typedef proto::unary_op<ichar_tag, proto::noop_tag> ianychar_p;
    typedef proto::unary_op<char, proto::noop_tag> chlit_p;
    typedef proto::unary_op<char const *, proto::noop_tag> szlit_p;
    typedef proto::nary_op<anychar_p, char> char_p;
    typedef proto::nary_op<ianychar_p, char, char> ichar_p;
    typedef proto::nary_op<anychar_p, char, char> char_range_p;
    typedef proto::unary_op<istring_tag, proto::noop_tag> ianystr_p;
    typedef proto::nary_op<ianystr_p, std::string, std::string> istr_p;
    typedef proto::unary_op<ichar_range_tag, proto::noop_tag> ianychar_range_p;
    typedef proto::nary_op<ianychar_range_p, char, char> ichar_range_p;

    proto::unary_op<ichar_tag, proto::noop_tag> const ichar_;
    proto::unary_op<istring_tag, proto::noop_tag> const istr_;
    proto::unary_op<ichar_range_tag, proto::noop_tag> const ichar_range_;

    namespace parser
    {
        // parse function for anychar_p
        template<typename Visitor>
        bool parse(anychar_p const &, Visitor &visitor)
        {
            if(visitor.first == visitor.second)
                return false;
            ++visitor.first;
            return true;
        }

        // parse function for char_p
        template<typename Visitor>
        bool parse(char_p const &p, Visitor &visitor)
        {
            if(visitor.first == visitor.second
              || *visitor.first != fusion::get<0>(p.args))
                return false;
            ++visitor.first;
            return true;
        }

        // parse function for bare character literals
        template<typename Visitor>
        bool parse(chlit_p const &p, Visitor &visitor)
        {
            return parser::parse(char_(p.arg), visitor);
        }

        inline bool char_icmp(char ch, char lo, char hi)
        {
            return ch == lo || ch == hi;
        }

        // case-insensitive character parser
        template<typename Visitor>
        bool parse(ichar_p const &p, Visitor &visitor)
        {
            if(visitor.first == visitor.second
              || !char_icmp(*visitor.first, fusion::get<0>(p.args), fusion::get<1>(p.args)))
                return false;
            ++visitor.first;
            return true;
        }

        template<typename FwdIter>
        inline bool string_cmp(char const *sz, FwdIter &begin, FwdIter end)
        {
            FwdIter tmp = begin;
            do if(!*sz)
            {
                begin = tmp;
                return true;
            } while(tmp != end && *sz++ == *tmp++);
            return false;
        }

        template<typename FwdIter>
        inline bool string_icmp(std::string const &lo, std::string const &hi, FwdIter &begin, FwdIter end)
        {
            BOOST_ASSERT(lo.size() == hi.size());
            FwdIter tmp = begin;
            std::string::const_iterator ilo = lo.begin(), elo = lo.end(), ihi = hi.begin();
            do if(ilo == elo)
            {
                begin = tmp;
                return true;
            } while(tmp != end && char_icmp(*tmp++, *ilo++, *ihi++));
            return false;
        }

        // string literal parser
        template<std::size_t N, typename Visitor>
        bool parse(proto::unary_op<char const[N], proto::noop_tag> const &p, Visitor &visitor)
        {
            return string_cmp(proto::arg(p), visitor.first, visitor.second);
        }

        template<typename Visitor>
        bool parse(szlit_p const &p, Visitor &visitor)
        {
            return string_cmp(proto::arg(p), visitor.first, visitor.second);
        }

        template<typename Visitor>
        bool parse(istr_p const &p, Visitor &visitor)
        {
            return string_icmp(fusion::get<0>(p.args), fusion::get<1>(p.args), visitor.first, visitor.second);
        }

        inline bool in_range(char ch, char lo, char hi)
        {
            return ch >= lo && ch <= hi;
        }

        inline bool in_irange(char ch, char lo, char hi)
        {
            return in_range(ch, lo, hi)
                || in_range(std::tolower(ch), lo, hi)
                || in_range(std::toupper(ch), lo, hi);
        }

        // parse function for char_range_p
        template<typename Visitor>
        bool parse(char_range_p const &p, Visitor &visitor)
        {
            BOOST_ASSERT(fusion::get<0>(p.args) <= fusion::get<1>(p.args));
            if(visitor.first == visitor.second
              || !in_range(*visitor.first, fusion::get<0>(p.args), fusion::get<1>(p.args)))
                return false;
            ++visitor.first;
            return true;
        }

        // parse function for ichar_range_p
        template<typename Visitor>
        bool parse(ichar_range_p const &p, Visitor &visitor)
        {
            BOOST_ASSERT(fusion::get<0>(p.args) <= fusion::get<1>(p.args));
            if(visitor.first == visitor.second
              || !in_irange(*visitor.first, fusion::get<0>(p.args), fusion::get<1>(p.args)))
                return false;
            ++visitor.first;
            return true;
        }

        // parse function for complemented thingies (where thingies are assumed 
        // to be 1 character wide).
        template<typename Arg, typename Visitor>
        bool parse(proto::unary_op<Arg, proto::complement_tag> const &p, Visitor &visitor)
        {
            Visitor tmp = visitor;
            if(parser::parse(proto::arg(p), tmp))
                return false;
            ++visitor.first;
            return true;
        }

        // parser for other unknown things, invoke proto::compile
        template<typename Rule, typename Visitor>
        bool parse(Rule const &rule, Visitor &visitor)
        {
            // had better not be a terminal, or we recurse forever
            typedef typename proto::tag_type<Rule>::type tag_type;
            BOOST_MPL_ASSERT_NOT((is_same<tag_type, proto::noop_tag>));
            BOOST_MPL_ASSERT_NOT((is_same<tag_type, proto::function_tag>));

            typename Visitor::first_type begin = visitor.first;
            if(proto::compile(rule, true, visitor, parser_tag()))
                return true;
            visitor.first = begin;
            return false;
        }

        // all parsers return bool
        struct parser_compiler_base
        {
            template<typename,typename,typename>
            struct apply
            {
                typedef bool type;
            };
        };

        // only invoke the next parser if all previous parsers have succeeded.
        template<typename Derived>
        struct parser_compiler : parser_compiler_base
        {
            template<typename Node, typename Visitor>
            static bool call(Node const &node, bool result, Visitor &visitor)
            {
                return result && Derived::parse(node, visitor);
            }
        };

        // dispatch to the correct free-function depending on the type of Node.
        struct primitive_compiler : parser_compiler<primitive_compiler>
        {
            template<typename Node, typename Visitor>
            static bool parse(Node const &node, Visitor &visitor)
            {
                return parser::parse(node, visitor);
            }
        };

        // for A | B, succeeds if either A or B matches at this point.
        struct alternate_compiler : parser_compiler<alternate_compiler>
        {
            template<typename Node, typename Visitor>
            static bool parse(Node const &node, Visitor &visitor)
            {
                return parser::parse(proto::left(node), visitor)
                    || parser::parse(proto::right(node), visitor);
            }
        };

        // for *A, greedily match A as many times as possible.
        struct kleene_compiler : parser_compiler<kleene_compiler>
        {
            template<typename Node, typename Visitor>
            static bool parse(Node const &node, Visitor &visitor)
            {
                while(parser::parse(proto::arg(node), visitor))
                    ;
                return true;
            }
        };

        // for +A, greedily match A one or more times.
        struct plus_compiler : parser_compiler<plus_compiler>
        {
            template<typename Node, typename Visitor>
            static bool parse(Node const &node, Visitor &visitor)
            {
                if(!parser::parse(proto::arg(node), visitor))
                    return false;
                while(parser::parse(proto::arg(node), visitor))
                    ;
                return true;
            }
        };

        // for !A, optionally match A.
        struct optional_compiler : parser_compiler<optional_compiler>
        {
            template<typename Node, typename Visitor>
            static bool parse(Node const &node, Visitor &visitor)
            {
                parser::parse(proto::arg(node), visitor);
                return true;
            }
        };

        // for (A - B), matches when A but not B matches.
        struct difference_compiler : parser_compiler<difference_compiler>
        {
            template<typename Node, typename Visitor>
            static bool parse(Node const &node, Visitor &visitor)
            {
                Visitor tmp1 = visitor, tmp2 = visitor;
                if(parser::parse(proto::left(node), tmp1) &&
                  !parser::parse(proto::right(node), tmp2))
                {
                    visitor = tmp1;
                    return true;
                }
                return false;
            }
        };
    } // namespace parser

    namespace no_case_
    {
        template<typename Arg>
        struct remove_case
        {
            typedef Arg type;

            static Arg const &call(Arg const &arg)
            {
                return arg;
            }
        };

        template<>
        struct remove_case<char_p>
        {
            typedef ichar_p type;

            static type call(char_p const &p)
            {
                char lo = std::tolower(fusion::get<0>(p.args));
                char hi = std::toupper(fusion::get<0>(p.args));
                return ichar_(lo, hi);
            }
        };

        template<>
        struct remove_case<chlit_p>
        {
            typedef ichar_p type;

            static type call(chlit_p const &p)
            {
                char lo = std::tolower(p.arg);
                char hi = std::toupper(p.arg);
                return ichar_(lo, hi);
            }
        };

        template<>
        struct remove_case<char_range_p>
        {
            typedef ichar_range_p type;

            static type call(char_range_p const &p)
            {
                char lo = fusion::get<0>(p.args);
                char hi = fusion::get<1>(p.args);
                return ichar_range_(lo, hi);
            }
        };

        std::string to_lower(std::string str)
        {
            for(std::string::iterator i = str.begin(); i != str.end(); ++i)
                *i = std::tolower(*i);
            return str;
        }

        std::string to_upper(std::string str)
        {
            for(std::string::iterator i = str.begin(); i != str.end(); ++i)
                *i = std::toupper(*i);
            return str;
        }

        template<>
        struct remove_case<szlit_p>
        {
            typedef istr_p type;

            static type call(szlit_p const &p)
            {
                return istr_(to_lower(proto::arg(p)), to_upper(proto::arg(p)));
            }
        };

        template<std::size_t N>
        struct remove_case<proto::unary_op<char const [N], proto::noop_tag> >
        {
            typedef istr_p type;

            static type call(proto::unary_op<char const [N], proto::noop_tag> const &p)
            {
                return istr_(to_lower(proto::arg(p)), to_upper(proto::arg(p)));
            }
        };

        struct no_case_compiler
        {
            template<typename Node, typename State, typename Visitor>
            struct apply
              : remove_case<Node>
            {
            };

            template<typename Node, typename State, typename Visitor>
            static typename remove_case<Node>::type
            call(Node const &node, State const &, Visitor &)
            {
                return remove_case<Node>::call(node);
            }
        };

        struct no_case_directive
        {
            template<typename Node>
            typename proto::compile_result<Node, mpl::void_, mpl::void_, no_case_tag>::type
            operator [](Node const &node) const
            {
                mpl::void_ null;
                return proto::compile(node, null, null, no_case_tag());
            }
        };
    }

    template<typename FwdIter, typename Rule>
    bool parse(FwdIter begin, FwdIter end, Rule const &rule)
    {
        std::pair<FwdIter,FwdIter> visitor(begin, end);
        return parser::parse(rule, visitor);
    }

    no_case_::no_case_directive const no_case = {};

}}

namespace boost { namespace proto
{
    // parsing rules
    template<>
    struct compiler<right_shift_tag, spirit2::parser_tag>
      : fold_compiler<spirit2::parser_tag>
    {};

    template<>
    struct compiler<bitor_tag, spirit2::parser_tag>
      : spirit2::parser::alternate_compiler
    {};

    template<>
    struct compiler<unary_star_tag, spirit2::parser_tag>
      : spirit2::parser::kleene_compiler
    {};

    template<>
    struct compiler<unary_plus_tag, spirit2::parser_tag>
      : spirit2::parser::plus_compiler
    {};

    template<>
    struct compiler<logical_not_tag, spirit2::parser_tag>
      : spirit2::parser::optional_compiler
    {};

    template<>
    struct compiler<subtract_tag, spirit2::parser_tag>
      : spirit2::parser::difference_compiler
    {};

    template<>
    struct compiler<function_tag, spirit2::parser_tag>
      : spirit2::parser::primitive_compiler
    {};

    template<>
    struct compiler<noop_tag, spirit2::parser_tag>
      : spirit2::parser::primitive_compiler
    {};

    template<>
    struct compiler<complement_tag, spirit2::parser_tag>
      : spirit2::parser::primitive_compiler
    {};

    // no_case_ transformation rules
    template<typename OpTag>
    struct compiler<OpTag, spirit2::no_case_tag>
      : pass_through_compiler<spirit2::no_case_tag>
    {};

    template<>
    struct compiler<noop_tag, spirit2::no_case_tag>
      : spirit2::no_case_::no_case_compiler
    {};

    template<>
    struct compiler<function_tag, spirit2::no_case_tag>
      : spirit2::no_case_::no_case_compiler
    {};
}}

using namespace boost;
using namespace spirit2;

template<typename T> void display_type(T const &) { std::cout << typeid(T).name() << std::endl; }

int main()
{
    std::string str("abcd");

    // This will fail:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end()
                   , char_ >> char_('a'))
              << std::endl;

    // This will succeed:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end()
                   , char_ >> char_('b') >> char_ >> 'd')
              << std::endl;

    // This will succeed:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end()
                   , 'a' >> ('c' >> char_ | 'b' >> char_('d') | 'b' >> char_('c')) >> 'd')
              << std::endl;

    // This will succeed:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end(), *(char_ - 'd'))
              << std::endl;

    // This will succeed:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end(), no_case[char_('A') >> 'B' >> "CD"])
              << std::endl;

    // This will succeed:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end(), no_case[*char_('A','Z')])
              << std::endl;

    literal<char> a = lit('a');
    literal<char const *> bcd = lit("bcd");

    // This will succeed:
    std::cout << "Result: " << std::boolalpha
              << spirit2::parse(str.begin(), str.end(), +~~a >> no_case[bcd])
              << std::endl;

    return 0;
}