一個實驗性的C++編譯期正則表達式parse工具

使用了C++17和gnu擴展

這個東西主要是用來在編譯期把正則表達式字元串字面量處理成正則表達式語法樹（表達式模板），然後運行期可以直接使用這棵語法樹來匹配文字了，避免了運行期編譯正則表達式的性能負擔，並且類型安全，語法有錯的話根本通不過編譯

畢竟99%的正則表達式使用場合都是可以編譯期確定整段表達式的

目前只支持三個基本元素：連接，或，克林閉包，不支持括弧，我也不是很想繼續寫下去

值得一提的是，我沒有使用傳統的模板元編程方法，即C++98就有的，使用模板類來搞事情，通過特化來分支，通過成員模板來模擬函數調用，而是使用了boost hana的思路，一種使用C++表達式來表現模板元編程邏輯的方法，藉助表達式和auto返回值推導，代碼更加友好

不說廢話，直接上代碼

首先是一點通用的東西

namespace mqn{nntemplate<char c>nstruct char_constant : std::integral_constant<char, c>n{n};nntemplate<class T, T c1, T c2>nconstexpr std::bool_constant<c1 == c2> operator==(std::integral_constant<T, c1>, std::integral_constant<T, c2>)n{n return{};n}nntemplate<class T, T c1, T c2>nconstexpr std::bool_constant<c1 != c2> operator!=(std::integral_constant<T, c1>, std::integral_constant<T, c2>)n{n return{};n}nntemplate<class T, T c1, T c2>nconstexpr std::bool_constant<(c1 > c2)> operator>(std::integral_constant<T, c1>, std::integral_constant<T, c2>)n{n return{};n}nntemplate<class T, T c1, T c2>nconstexpr std::bool_constant<(c1 >= c2)> operator>=(std::integral_constant<T, c1>, std::integral_constant<T, c2>)n{n return{};n}nntemplate<class T, T c1, T c2>nconstexpr std::bool_constant<(c1 < c2)> operator<(std::integral_constant<T, c1>, std::integral_constant<T, c2>)n{n return{};n}nntemplate<class T, T c1, T c2>nconstexpr std::bool_constant<(c1 <= c2)> operator<=(std::integral_constant<T, c1>, std::integral_constant<T, c2>)n{n return{};n}nntemplate<bool b1, bool b2>nconstexpr std::bool_constant<b1 && b2> operator&&(std::bool_constant<b1>, std::bool_constant<b2>)n{n return{};n}nntemplate<bool b1, bool b2>nconstexpr std::bool_constant<b1 || b2> operator||(std::bool_constant<b1>, std::bool_constant<b2>)n{n return{};n}nntemplate<bool v, class T1, class T2>nconstexpr decltype(auto) cond(std::bool_constant<v>, T1 a, T2 b)n{n if constexpr (v)n {n return a;n }n elsen {n return b;n }n}nntemplate<class Curr, class Cond, class Iter>nconstexpr decltype(auto) iter(Curr i, Cond c, Iter e)n{n //static_assert(c(i).value);n if constexpr (c(i).value)n {n return iter(e(i), c, e);n }n elsen {n return i;n }n}nn} //namespace mqn

然後是本體：

namespace mqn{nntemplate<char c>nconstexpr static auto cc = char_constant<c>{};nntemplate<char... chars>nstruct char_sequencen{n template<size_t i>n constexpr static decltype(auto) get()n {n static_assert(i < sizeof...(chars), "internal error");n return char_constant<std::get<i>(std::make_tuple(chars...))>{};n }n};nntemplate<class Sequence, size_t _i, class Result>nstruct parse_resultn{n constexpr static decltype(auto) sequence()n {n return Sequence{};n }nn constexpr static decltype(auto) get()n {n return Sequence::template get<_i>();n }nn constexpr static decltype(auto) peek()n {n return Sequence::template get<_i + 1>();n }nn constexpr static decltype(auto) result()n {n return Result{};n }nn constexpr static decltype(auto) forward()n {n return parse_result<Sequence, _i + 1, Result>{};n }nn template<class R>n constexpr static decltype(auto) result(R)n {n return parse_result<Sequence, _i, R>{};n }n};nntemplate<class Derived>nstruct regexn{n};nntemplate<char c>nstruct match : regex<match<c>>n{n};nntemplate<char c>nconstexpr decltype(auto) mkmatch(char_constant<c>)n{n return match<c>{};n}nntemplate<char c>nstruct kleene : regex<kleene<c>>n{n};nntemplate<char c>nconstexpr decltype(auto) mkkleene(char_constant<c>)n{n return kleene<c>{};n}nntemplate<class... Regexes>nstruct concat : regex<concat<Regexes...>>n{n};nntemplate<class... Ts>nconstexpr decltype(auto) mkconcat(regex<Ts>...)n{n return concat<Ts...>{};n}nntemplate<class... Rs, class... Ts>nconstexpr decltype(auto) mkconcat(concat<Rs...>, regex<Ts>...)n{n return concat<Rs..., Ts...>{};n}nntemplate<class... Regexes>nstruct alter : regex<alter<Regexes...>>n{n};nntemplate<class... Ts>nconstexpr decltype(auto) mkalter(regex<Ts>...)n{n return alter<Ts...>{};n}nntemplate<class... Rs, class... Ts>nconstexpr decltype(auto) mkalter(alter<Rs...>, regex<Ts>...)n{n return alter<Rs..., Ts...>{};n}nnstruct regex_parsern{n template<class Seq>n constexpr static decltype(auto) parse(Seq s)n {n return parse_alternative(parse_result<Seq, 0, void>{});n }nprivate:n template<class ParseResult>n constexpr static decltype(auto) parse_alternative(ParseResult r)n {n return iter(parse_concatination(r),n [](auto res)n {n return res.get() != cc<0>;n },n [](auto res)n {n static_assert((res.get() == cc<|>).value);n auto e = parse_concatination(res.forward());n return e.result(mkalter(res.result(), e.result()));n });n }nn template<class ParseResult>n constexpr static decltype(auto) parse_concatination(ParseResult r)n {n return iter(parse_kleene(r),n [](auto res)n {n return (res.get() != cc<0>) && (res.get() != cc<|>);n },n [](auto res)n {n auto e = parse_kleene(res);n return e.result(mkconcat(res.result(), e.result()));n });n /* 相當於n auto regex = mkconcat(parse_kleene(r));n for (;;)n {n if (r.get() ！= 0 && r.get() != |)n {n regex = mkconcat(regex, parse_kleene(r.forward()));n }n elsen {n return regex;n }n }n */n }nn template<class ParseResult>n constexpr static decltype(auto) parse_kleene(ParseResult r)n {n auto token = r.get();n auto next = r.peek();n return cond(next == cc<*>,n [=] { return r.forward().forward().result(mkkleene(token)); },n [=] { return r.forward().result(mkmatch(token)); })();n }nn};nntemplate<class TChar, TChar... chars>nconstexpr decltype(auto) operator"" _regex()n{n return regex_parser::parse(char_sequence<chars..., 0>{}).result();n}nn}n

哦順便說上面那個operator""_regex是gnu的擴展，還挺好用的

驗證一下結果：

auto a = "ab*|c"_regex;nstd::cout << typeid(a).name() << "n";n

請注意我這裡使用的是typeid，這就證明了a的類型在編譯期已經確定了

輸出的東西demangle一下

mq::alter<mq::concat<mq::match<(char)97>, mq::kleene<(char)98> >, mq::match<(char)99> >n

完美

簡單總結一下，這一大堆東西，看起來像普通的代碼，實際上都是元編程。這裡面所有的值，他是什麼，我都是不關心的，我甚至不關係表達式是否被求值，lambda是否被真正的調用。我關心的，是他們的類型，這是編譯期可以確定的，而這就是boost hana等現代TMP庫的設計思路。

各位覺得知乎的閱讀體驗太差的話，歡迎來我的博客，我會在近期把這篇文章寫詳細了更新上去。

我的博客是存粹的技術分享，沒有吸粉和變現的內容，歡迎大家關注。

推薦閱讀：