parse.hpp

Go to the documentation of this file.

#pragma once

#include <xtd/xtd.hpp>

#include <memory>
#include <regex>

#include <xtd/meta.hpp>

namespace xtd{

  namespace parse{


#define STRING_(x) \
      namespace _{ char x[] = #x; } \
      using x = xtd::parse::string< decltype(_::x), _::x>;

#define STRING(_name, _value) \
      namespace _{ char _name[] = _value; } \
      using _name = xtd::parse::string< decltype(_::_name), _::_name>;


#define CHARACTER_(_name, _value) \
  namespace _{} \
  using _name = xtd::parse::character<_value>

#define REGEX(_name, _value) \
      namespace _{ char _name[] = _value; } \
      using _name = xtd::parse::regex< decltype(_::_name), _::_name>;


    class rule_base{
    public:
      using pointer_type = std::shared_ptr<rule_base>;
      using vector_type = std::vector<pointer_type>;

      template <typename ... _ChildRuleTs>
      explicit rule_base(_ChildRuleTs&& ... oChildRules) : _Items{ std::forward<_ChildRuleTs>(oChildRules)... }{}

      virtual ~rule_base() = default;
      virtual bool isa(const std::type_info& oType) const = 0;
      virtual const std::type_info& type() const = 0;
      const vector_type& items() const{ return _Items; }

    protected:
      vector_type _Items;
    };


    template <typename _DeclT, typename _ImplT = _DeclT>
    class rule : public rule_base{
    public:
      using decl_type = _DeclT;
      using impl_type = _ImplT;
      using rule_type = rule<_DeclT, _ImplT>;

      template <typename ... _ChildRuleTs>
      explicit rule(_ChildRuleTs&& ... oChildRules) : rule_base(std::forward<_ChildRuleTs>(oChildRules)...){}

      virtual ~rule() = default;

      virtual bool isa(const std::type_info& oType) const override{
        return (typeid(rule) == oType) || (typeid(decl_type) == oType) || (typeid(impl_type) == oType) || (typeid(rule_base) == oType);
      }

      virtual const std::type_info& type() const override{
        return typeid(_DeclT);
      }

    };


    template <typename ...> class and_;
#if (!DOXY_INVOKED)
    template <> class and_<> : public rule<and_<>>{
    public:
      using _super_t = rule<and_<>>;
      template <typename ... _ChildRuleTs>
      explicit and_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}
    };

    template <typename _HeadT, typename ... _TailT> class and_<_HeadT, _TailT...> : public rule<and_<_HeadT, _TailT...>>{
    public:
      using _super_t = rule<and_<_HeadT, _TailT...>>;
      template <typename ... _ChildRuleTs>
      explicit and_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}

    };
#endif

    template <typename ...> class or_;
#if (!DOXY_INVOKED)
    template <> class or_<> : public rule<or_<>>{
    public:
      using _super_t = rule<or_<>>;
      template <typename ... _ChildRuleTs>
      explicit or_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}
    };

    template <typename _HeadT, typename ... _TailT> class or_<_HeadT, _TailT...> : public rule<or_<_HeadT, _TailT...>>{
    public:
      using _super_t = rule<or_<_HeadT, _TailT...>>;
      template <typename ... _ChildRuleTs>
      explicit or_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}
    };
#endif


    template <typename _Ty> class one_or_more_ : public rule<one_or_more_<_Ty>>{
    public:
      using _super_t = rule<one_or_more_<_Ty>>;
      template <typename ... _ChildRuleTs>
      explicit one_or_more_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}
    };



    template <typename _Ty> class zero_or_more_ : public rule<zero_or_more_<_Ty>>{
    public:
      using _super_t = rule<zero_or_more_<_Ty>>;
      template <typename ... _ChildRuleTs>
      explicit zero_or_more_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}
    };


    template <typename _Ty> class zero_or_one_ : public rule<zero_or_one_<_Ty>>{
    public:
      using _super_t = rule<zero_or_one_<_Ty>>;
      template <typename ... _ChildRuleTs>
      explicit zero_or_one_(_ChildRuleTs&& ... oChildRules) : _super_t(std::forward<_ChildRuleTs>(oChildRules)...){}
    };


    template <char..._Ch> class whitespace{
    public:
      using whitespace_type = whitespace<_Ch...>;
    };


    template <typename _Ty, _Ty &> class string;
  #if (!DOXY_INVOKED)
    template <size_t _len, char(&_str)[_len]> class string<char[_len], _str> : public rule<string<char[_len], _str>>{
    public:
      using _super_t = rule<string<char[_len], _str>>;
      static constexpr size_t length = _len;
      string() = default;
    };
  #endif


    template <char _value> class character : public rule<character<_value>>{};

    template <typename _Ty, _Ty &> class regex;
  #if (!DOXY_INVOKED)
    template <size_t _len, char(&_str)[_len]> class regex<char[_len], _str> : public rule<regex<char[_len], _str>>{
    public:
      using _super_t = rule<regex<char[_len], _str>>;
      static constexpr size_t length = _len;
      explicit regex(const std::string& newval) : _super_t(), _value(newval){}
      const std::string& value() const{ return _value; }
    protected:
      std::string _value;
    };
  #endif

#if (!DOXY_INVOKED)

    namespace _{

      template <typename _DeclT, typename _ImplT, bool _IgnoreCase, typename _WhitespaceT> class parse_helper;

      template <typename _DeclT, size_t _len, char(&_str)[_len], typename _WhitespaceT>
      class parse_helper<_DeclT, parse::string<char[_len], _str>, false, _WhitespaceT>{
      public:
        template <typename _IteratorT> static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end){
          _IteratorT oCurr = begin;

          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);

          rule_base::pointer_type oRet(nullptr);
          for (size_t i = 0; (i < (_len-1)) && (oCurr < end); ++i, ++oCurr){
            if (_str[i] != *oCurr){
              return rule_base::pointer_type(nullptr);
            }
          }

          /*
          Problem: The string comparison algorithms compare character by character and skip any leading or trailing whitespace between terminals.
            Rules 'ABC' + 'XYZ' maybe defined expecting the two terminals be separated by whitespace but this algorithm could parse the string 'ABCXYZ' as two separate terminals.
            There's a number of traditional approaches to solving this such as tokenizing before parsing or creating parse tables.
            A proper handling would compound the complexity of this library beyond it's intended scope, there are plenty of complex parsers around.
            Currently, the last character parsed is checked against the next character in the stream to see if they're of the same 'class' and fail if so.
            This isn't ideal because it maybe perfectly valid in some grammars to expect 'ABCXYZ' to appear in the input stream yet successfully parse into independent terminals.
            This library assumes contiguous alpha-numeric terminals constitute a single terminal so the input stream of 'ABCXYZ' will fail to parse without grammar definition trickery
          */
          if (oCurr < end && isalnum(*oCurr) && isalnum(_str[_len - 2])){
            return rule_base::pointer_type(nullptr);
          }
          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);

          begin = oCurr;
          return rule_base::pointer_type(new _DeclT);
        }
      };


      template <typename _DeclT, size_t _len, char(&_str)[_len], typename _WhitespaceT>
      class parse_helper<_DeclT, parse::string<char[_len], _str>, true, _WhitespaceT>{
      public:

        template <typename _IteratorT>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end){
          _IteratorT oCurr = begin;

          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);

          rule_base::pointer_type oRet(nullptr);
          for (size_t i = 0; (i < _len-1) && (oCurr < end); ++i, ++oCurr){
            if (tolower(_str[i]) != tolower(*oCurr)){
              return rule_base::pointer_type(nullptr);
            }
          }
          if (oCurr < end && isalnum(*oCurr) && isalnum(_str[_len - 2])){
            return rule_base::pointer_type(nullptr);
          }

          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);

          begin = oCurr;
          return rule_base::pointer_type(new _DeclT);
        }

      };

      template <typename _DeclT, size_t _len, char(&_str)[_len], bool _IgnoreCase, typename _WhitespaceT>
      class parse_helper<_DeclT, parse::regex<char[_len], _str>, _IgnoreCase, _WhitespaceT>{
      public:

        template <typename _IteratorT>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end){
          _IteratorT oCurr = begin;

          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);

          static std::regex oRE(_str, std::regex_constants::ECMAScript | std::regex_constants::nosubs | std::regex_constants::optimize | (_IgnoreCase ? std::regex_constants::icase : std::regex_constants::optimize));
          std::match_results<std::string::iterator> oMatch;
          if (!std::regex_search(oCurr, end, oMatch, oRE, std::regex_constants::match_continuous | std::regex_constants::format_first_only)){
            return rule_base::pointer_type(nullptr);
          }
          oCurr += oMatch[0].length();

          if (oCurr < end && isalnum(*oCurr) && isalnum(_str[_len - 1])){
            return rule_base::pointer_type(nullptr);
          }


          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);

          begin = oCurr;
          return rule_base::pointer_type(new _DeclT(oMatch[0].str()));

        }

      };

      template <bool _IgnoreCase>
      class parse_helper<whitespace<>, void, _IgnoreCase, void>{
      public:
        template <typename _IteratorT>
        static bool parse(_IteratorT&, _IteratorT&){ return false; }
      };

      template <char _HeadCH, char... _TailCH, bool _IgnoreCase>
      class parse_helper<whitespace<_HeadCH, _TailCH...>, void, _IgnoreCase, void>{
      public:
        template <typename _IteratorT>
        static bool parse(_IteratorT& begin, _IteratorT& end){
          _IteratorT oCurr = begin;

          while (oCurr < end){
            if (*oCurr == _HeadCH){
              oCurr++;
            }else if (parse_helper<whitespace<_TailCH...>, void, _IgnoreCase, void>::parse(oCurr, end)){
              //do nothing
            }else{
              break;
            }
          }
          begin = oCurr;
          return false;
        }
      };

      //character
      template <typename _DeclT, char _Ch, typename _WhitespaceT>
      class parse_helper<_DeclT, character<_Ch>, true, _WhitespaceT>{
      public:

        template <typename _IteratorT>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end){
          _IteratorT oCurr = begin;
          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);
          if (lower_case<char, _Ch>::value != tolower(*oCurr)){
            return rule_base::pointer_type(nullptr);
          }
          ++oCurr;
          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);
          begin = oCurr;
          return rule_base::pointer_type(new character<_Ch>);
        }

      };

      template <typename _DeclT, char _Ch, typename _WhitespaceT>
      class parse_helper<_DeclT, character<_Ch>, false, _WhitespaceT>{
      public:

        template <typename _IteratorT>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end){
          _IteratorT oCurr = begin;
          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);
          if (_Ch != oCurr[0]){
            return rule_base::pointer_type(nullptr);
          }
          ++oCurr;
          parse_helper< _WhitespaceT, void, true, void>::parse(oCurr, end);
          begin = oCurr;
          return rule_base::pointer_type(new character<_Ch>);
        }

      };


      //and
      template <typename _DeclT, bool _IgnoreCase, typename _WhitespaceT >
      class parse_helper < _DeclT, parse::and_<>, _IgnoreCase, _WhitespaceT>{
      public:

        template <typename _IteratorT, typename ... _ChildRuleTs>
        static rule_base::pointer_type parse(_IteratorT& , _IteratorT& , _ChildRuleTs&& ... oChildRules){
          return rule_base::pointer_type(new _DeclT(std::forward<_ChildRuleTs>(oChildRules)...));
        }

      };

      template <typename _DeclT, typename _HeadT, typename ... _TailT, bool _IgnoreCase, typename _WhitespaceT >
      class parse_helper < _DeclT, parse::and_<_HeadT, _TailT...>, _IgnoreCase, _WhitespaceT>{
      public:

        template <typename _IteratorT, typename ... _ChildRuleTs>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end, _ChildRuleTs&& ... oChildRules){
          _IteratorT oBegin = begin;
          auto oItem = parse_helper<_HeadT, typename _HeadT::impl_type, _IgnoreCase, _WhitespaceT>::parse(oBegin, end);
          if (!oItem){
            return oItem;
          }
          oItem = parse_helper<_DeclT, parse::and_<_TailT...>, _IgnoreCase, _WhitespaceT>::parse(oBegin, end, std::forward<_ChildRuleTs>(oChildRules)..., oItem);
          if (oItem){
            begin = oBegin;
          }
          return oItem;
        }

      };


      template <typename _DeclT, bool _IgnoreCase, typename _WhitespaceT >
      class parse_helper < _DeclT, parse::or_<>, _IgnoreCase, _WhitespaceT>{
      public:

        template <typename _IteratorT, typename ... _ChildRuleTs>
        static rule_base::pointer_type parse(_IteratorT& , _IteratorT& , _ChildRuleTs ... ){
          return rule_base::pointer_type(nullptr);
        }

      };

      template <typename _DeclT, typename _HeadT, typename ... _TailT, bool _IgnoreCase, typename _WhitespaceT >
      class parse_helper < _DeclT, parse::or_<_HeadT, _TailT...>, _IgnoreCase, _WhitespaceT>{
      public:

        template <typename _IteratorT, typename ... _ChildRuleTs>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end, _ChildRuleTs&& ... oChildRules){
          _IteratorT oBegin = begin;
          auto oItem = parse_helper<_HeadT, typename _HeadT::impl_type, _IgnoreCase, _WhitespaceT>::parse(oBegin, end);
          if (oItem){
            begin = oBegin;
            return rule_base::pointer_type(new _DeclT(oItem));
          }
          oItem = parse_helper<_DeclT, parse::or_<_TailT...>, _IgnoreCase, _WhitespaceT>::parse(oBegin, end, std::forward<_ChildRuleTs>(oChildRules)..., oItem);
          if (oItem){
            begin = oBegin;
          }
          return oItem;
        }

      };



      template <typename _DeclT, typename _Ty, bool _IgnoreCase, typename _WhitespaceT >
      class parse_helper < _DeclT, parse::zero_or_more_<_Ty>, _IgnoreCase, _WhitespaceT>{
      public:

        template <typename _IteratorT, typename ... _ChildRuleTs>
        static rule_base::pointer_type parse(_IteratorT& begin, _IteratorT& end, _ChildRuleTs&& ... oChildRules){
          _IteratorT oBegin = begin;
          auto oItem = parse_helper<_Ty, typename _Ty::impl_type, _IgnoreCase, _WhitespaceT>::parse(oBegin, end);
          if (!oItem){
            return rule_base::pointer_type(new _DeclT(std::forward<_ChildRuleTs>(oChildRules)...));
          }
          return parse_helper<_DeclT, parse::zero_or_more_<_Ty>, _IgnoreCase, _WhitespaceT>::parse(oBegin, end, std::forward<_ChildRuleTs>(oChildRules)..., oItem);
        }

      };
    }
#endif
  }
  template <typename _RuleT, bool _IgnoreCase = false, typename _WhitespaceT = xtd::parse::whitespace<>> class parser {
  public:

    template <typename _IteratorT> static parse::rule_base::pointer_type parse(_IteratorT begin, _IteratorT end) {
      _IteratorT oBegin = begin;
      _IteratorT oEnd = end;
      return parse::_::parse_helper<_RuleT, typename _RuleT::impl_type, _IgnoreCase, _WhitespaceT>::parse(oBegin, oEnd);
    }

  };

}