Regex Generator in C++

Question

So I am writing an XML parser, and I'm using regexes to do some pattern matching during parsing. However, writing longer regexes quickly became a bit boring, annoying and just confusing. So I thought to myself: "Wouldn't it be a fun little project to make a small library that helps me build these regexes?" I decided to go for it, and a few hours later, it was done. I'm mainly looking for advice on design here, though implementation issues are certainly welcome too. The main thing I am not so happy with is the char_traits struct. If there is a better way to do this, I will gladly implement it. Code:

#ifndef MVG_REGEX_GENERATOR_HPP_
#define MVG_REGEX_GENERATOR_HPP_

#include <regex>
#include <string>
#include <string_view>

namespace mvg {

namespace regex {

template<typename char_t>
struct char_traits;

template<>
struct char_traits<char> : public std::char_traits<char> {
    struct braces {
        struct square {
            static constexpr char open = '[';
            static constexpr char close = ']';
        };

        struct round {
            static constexpr char open = '(';
            static constexpr char close = ')';
        };

        struct curly {
            static constexpr char open = '{';
            static constexpr char close = '}';
        };
    };

    static constexpr char minus_sign = '-';
    static constexpr char plus = '+';
    static constexpr char or_sign = '|';
    static constexpr char power_sign = '^';
    static constexpr char star = '*';
    static constexpr char comma = ',';

        static constexpr char backslash = '\\';
    static constexpr char forwardslash = '/';

    static constexpr char question_mark = '?';
    static constexpr char colon = ':';

    static constexpr char s = 's';
    static constexpr char w = 'w';
    static constexpr char d = 'd';

    static constexpr char S = 'S';
    static constexpr char W = 'W';
    static constexpr char D = 'D';
};

template<>
struct char_traits<wchar_t> : public std::char_traits<wchar_t> {
    struct braces {
        struct square {
            static constexpr wchar_t open = L'[';
            static constexpr wchar_t close = L']';
        };

        struct round {
            static constexpr wchar_t open = L'(';
            static constexpr wchar_t close = L')';
        };

        struct curly {
            static constexpr wchar_t open = L'{';
            static constexpr wchar_t close = L'}';
        };
    };

    static constexpr wchar_t minus_sign = L'-';
    static constexpr wchar_t plus = L'+';
    static constexpr wchar_t or_sign = L'|';
    static constexpr wchar_t power_sign = L'^';
    static constexpr wchar_t star = L'*';
    static constexpr wchar_t comma = L',';

    static constexpr wchar_t backslash = L'\\';
    static constexpr wchar_t forwardslash = L'/';

    static constexpr wchar_t question_mark = L'?';
    static constexpr wchar_t colon = L':';

    static constexpr wchar_t s = L's';
    static constexpr wchar_t w = L'w';
    static constexpr wchar_t d = L'd';

    static constexpr wchar_t S = L'S';
    static constexpr wchar_t W = L'W';
    static constexpr wchar_t D = L'D';
};

template<typename char_t, typename traits = char_traits<char_t>>
class regex_element {
public:
    using string_t = std::basic_string<char_t, std::char_traits<char_t>>;

    regex_element(
        std::basic_string_view<char_t, std::char_traits<char_t>> reg_str) {
        str_ = reg_str;
    }

    regex_element(regex_element const&) = default;
    regex_element(regex_element&&) = default;

    regex_element& operator=(regex_element const&) = default;
    regex_element& operator=(regex_element&&) = default;

    string_t str() const { return str_; }

private:
    string_t str_;
};

template<typename char_t, typename traits = char_traits<char_t>>
class basic_regex_chain_holder {
public:
    using string_t = std::basic_string<char_t, std::char_traits<char_t>>;
    using string_view_t =
        std::basic_string_view<char_t, std::char_traits<char_t>>;
    using regex_element_t = regex_element<char_t, traits>;

    basic_regex_chain_holder(string_view_t reg_str) : str_(reg_str) {}
    basic_regex_chain_holder(basic_regex_chain_holder const&) = default;
    basic_regex_chain_holder(basic_regex_chain_holder&&) = default;

    basic_regex_chain_holder&
    operator=(basic_regex_chain_holder const&) = default;
    basic_regex_chain_holder& operator=(basic_regex_chain_holder&&) = default;

    string_t str() const { return str_; }

    //@return: *this to be able to chain this operation
    basic_regex_chain_holder& then_match(regex_element_t const& elem) {
        str_ += elem.str();
        return *this;
    }

private:
    string_t str_;
};

template<typename char_t, typename traits = char_traits<char_t>>
class basic_regex_generator {
public:
    using string_t = std::basic_string<char_t, std::char_traits<char_t>>;
    using string_view_t =
        std::basic_string_view<char_t, std::char_traits<char_t>>;
    using regex_element_t = regex_element<char_t, traits>;
    using regex_chain_holder_t = basic_regex_chain_holder<char_t, traits>;

    basic_regex_generator() = default;
    basic_regex_generator(basic_regex_generator const&) = default;
    basic_regex_generator(basic_regex_generator&&) = default;

    basic_regex_generator& operator=(basic_regex_generator const&) = default;
    basic_regex_generator& operator=(basic_regex_generator&&) = default;

    static regex_element_t match_range(char_t start, char_t end) {
        // Build a regex_element in the format of [start-end]
        return regex_element_t(string_t{} + traits::braces::square::open +
                               start + traits::minus_sign + end +
                               traits::braces::square::close);
    }

    // RegElement is either a regex_element_t or a regex_chain_holder_t
    template<typename RegElementA, typename RegElementB>
    static regex_element_t match_or(RegElementA const& a,
                                    RegElementB const& b) {
        // Ensure RegElementA and RegElementB are of the correct types.
        // Templating this function saves us writing 4 overloads for every
        // possible combination
        static_assert((
            std::is_same_v<RegElementA, regex_element_t> ||
            std::is_same_v<
                RegElementA,
                regex_chain_holder_t>)&&(std::is_same_v<RegElementB,
                                                        regex_element_t> ||
                                         std::is_same_v<RegElementB,
                                                        regex_chain_holder_t>));

        return regex_element_t(a.str() + traits::or_sign + b.str());
    }

    static regex_element_t match_any() {
        return regex_element_t(string_t(1, '.'));
    }

    static regex_element_t match_character(char_t ch) {
        return regex_element_t(string_t{} + ch);
    }

    static regex_element_t match_string(string_view_t str) {
        return regex_element_t(str);
    }

    static regex_element_t match_space() {
        return regex_element_t(string_t{} + traits::backslash + traits::s);
    }

    static regex_element_t match_alpha_char() {
        return regex_element_t(string_t{} + traits::backslash + traits::w);
    }

    static regex_element_t match_digit() {
        return regex_element_t(string_t{} + traits::backslash + traits::d);
    }

    static regex_element_t match_not_space() {
        return regex_element_t(string_t{} + traits::backslash + traits::S);
    }

    static regex_element_t match_not_alpha_char() {
        return regex_element_t{string_t{} + traits::backslash + traits::W};
    }

    static regex_element_t match_not_digit() {
        return regex_element_t{string_t{} + traits::backslash + traits::D};
    }

    static regex_element_t match_any_of(string_view_t chars) {
        return regex_element_t(string_t{} + traits::braces::square::open +
                               chars.data() + traits::braces::square::close);
    }

    static regex_element_t match_none_of(string_view_t chars) {
        return regex_element_t(string_t{} + traits::braces::square::open +
                               traits::power_sign + chars.data() +
                               traits::braces::square::close);
    }

    static regex_element_t match_escaped_char(char_t ch) {
        return regex_element_t(string_t{} + traits::backslash + ch);
    }

    template<typename RegElement>
    static regex_element_t match_zero_or_more(RegElement const& to_match) {
        static_assert(std::is_same_v<RegElement, regex_element_t> ||
                      std::is_same_v<RegElement, regex_chain_holder_t>);

        return regex_element_t(to_match.str() + traits::star);
    }

    template<typename RegElement>
    static regex_element_t match_one_or_more(RegElement const& to_match) {
        static_assert(std::is_same_v<RegElement, regex_element_t> ||
                      std::is_same_v<RegElement, regex_chain_holder_t>);

        return regex_element_t(to_match.str() + traits::plus);
    }

    template<typename RegElement>
    static regex_element_t match_zero_or_one(RegElement const& to_match) {
        static_assert(std::is_same_v<RegElement, regex_element_t> ||
                      std::is_same_v<RegElement, regex_chain_holder_t>);

        return regex_element_t(to_match.str() + traits::question_mark);
    }

    template<typename RegElement>
    static regex_element_t match_n(RegElement const& to_match, std::size_t n) {
        static_assert(std::is_same_v<RegElement, regex_element_t> ||
                      std::is_same_v<RegElement, regex_chain_holder_t>);
        return regex_element_t(to_match.str() + traits::braces::curly::open +
                               std::to_string(n) +
                               traits::braces::curly::close);
    }

    template<typename RegElement>
    static regex_element_t match_n_or_more(RegElement const& to_match,
                                           std::size_t n) {
        static_assert(std::is_same_v<RegElement, regex_element_t> ||
                      std::is_same_v<RegElement, regex_chain_holder_t>);
        return regex_element_t(to_match.str() + traits::braces::curly::open +
                               std::to_string(n) + traits::comma +
                               traits::braces::curly::close);
    }

    // Grouping functionality

    // non-capturing group
    static regex_element_t match_group(regex_element_t to_group) {
        return regex_element_t(string_t{} + traits::braces::round::open +
                               traits::question_mark + traits::colon +
                               to_group.str() + traits::braces::round::close);
    }

    static regex_element_t match_group(regex_chain_holder_t to_group) {
        return regex_element_t(string_t{} + traits::braces::round::open +
                               traits::question_mark + traits::colon +
                               to_group.str() + traits::braces::round::close);
    }

    static regex_element_t capture_group(regex_element_t const& to_capture) {
        return regex_element_t(traits::braces::round::open + to_capture.str() +
                               traits::braces::round::close);
    }

    // Overload to allow capturing multiple elements. Call this like:
    // .then_match(
    // regex_generator::capture_group(
    //      regex_generator::create_regex()
    //      .then_match(regex_generator::match_range('a', 'z'))
    //      .then_match(regex_generator::match_space())
    // ));
    static regex_element_t
    capture_group(regex_chain_holder_t const& to_capture) {
        return regex_element_t(traits::braces::round::open + to_capture.str() +
                               traits::braces::round::close);
    }

    //@return: A regex chain holder object that is used to build the regex
    regex_chain_holder_t create_regex() { return regex_chain_holder_t{""}; }

    regex_chain_holder_t create_regex_from_string(string_view_t initial_reg) {
        return regex_chain_holder_t{initial_reg};
    }

private:
    static string_t escape(char_t c) {
        return string_t(1, traits::backslash) + c;
    }
};

using regex_generator = basic_regex_generator<char, char_traits<char>>;
using wregex_generator = basic_regex_generator<wchar_t, char_traits<wchar_t>>;

} // namespace regex

} // namespace mvg

#endif

GitHub link here

I took the "features" from the cheatsheet on https://regexr.com/

Example usage (also found on GitHub)

 mvg::regex::regex_generator generator;
 using mvg::regex::regex_generator;

 auto regex = generator.create_regex()
                     .then_match(regex_generator::match_range('a', 'z'))
                     .then_match(regex_generator::match_string("XXX"))
                     .then_match(regex_generator::match_space())
                     .then_match(regex_generator::match_group(
                         generator.create_regex()
                             .then_match(regex_generator::match_string("Hello"))
                             .then_match(regex_generator::match_space())))
                     .then_match(regex_generator::match_any_of("abcdef"))
                     .then_match(regex_generator::match_none_of("qreoi"))
                     .then_match(regex_generator::match_zero_or_more(
                         regex_generator::match_range('a', 'z')));
std::regex regex_obj(regex.str());
//Use regex_obj here

I should probably add that I’m only going to use regexes to parse small parts of the XML, not the entire document. — MivVG
– MivVG, Commented Feb 5, 2019 at 17:56

Jerry Coffin · Accepted Answer · 2019-02-07 10:53:39Z

First, I'd note that I have a fair amount of sympathy for Quuzplusone's position.

Nonetheless, I can see some situations in which it could be somewhat handy to generate regexes, especially if (for example) you want to start with a number of fragments, and use loops (or whatever) to put them together into complete regexes, that then get tested.

However, you seem to be putting a lot of effort into building something that lets you use .then_match... syntax just to concatenate some strings together.

I also find the regex_generator::match_* syntax excessively verbose and clumsy.

While I can certainly sympathize with the notion of isolating the necessary literals into traits classes, I'm not convinced that the traits classes you've defined are the cleanest way to accomplish that (something you already seem to believe).

It seems to me that when all you're really doing is generating and concatenating strings, you can make a lot better use of existing classes to handle that--you can use normal string concatenation, or you can use a stringstream to concatenate strings together.

Using that basic approach, I slapped together enough of an implementation to handle your example:

#include <string>
#include <regex>
#include <iostream>
#include <locale>

namespace match {   
    template <class T>
     T W(char in) { 
         static auto& f = std::use_facet<std::ctype<T>>(std::locale());
         return f.widen(in);
     }

     template <class T>
     std::basic_string<T> W(char const* in) {
         static T ret[3];
         static auto& f = std::use_facet<std::ctype<T>>(std::locale());
         f.widen(in, in+2, ret);
         return std::basic_string<T>(ret);
     }

    template <class T>
    std::basic_string<T> range(T beg, T end) {
        return  std::basic_string<T>(1, W<T>('[')) + beg + W<T>('-') + end + W<T>(']');
    }

    template <class T>
    std::basic_string<T> literal(std::basic_string<T> const& s) { return s; }

    template <class T>
    std::basic_string<T> literal(T const* s) { return s; }

    template <class T>
    std::basic_string<T> group(std::basic_string<T> const &s) { return W<T>("\\(") + s + W<T>("\\)"); }

    template <class T>
    std::basic_string<T> group(T const* s) { return group(std::basic_string<T>(s)); }

    template <class T>
    std::basic_string<T> any_of(std::basic_string<T> const &s) { return W<T>('[') + s + W<T>(']'); }

    template <class T>
    std::basic_string<T> any_of(T const* s) { return any_of(std::basic_string<T>(s)); }

    template <class T>
    std::basic_string<T> none_of(std::basic_string<T> const &s) { return W<T>("[^") + s + W<T>("]"); }

    template <class T>
    std::basic_string<T> none_of(T const* s) { return none_of(std::basic_string<T>(s)); }

    template <class T>
    std::basic_string<T> arbno(std::basic_string<T> const &s) { return s + W<T>('*'); }

    template <class T>
    std::basic_string<T> arbno(T const* s) { return arbno(std::basic_string<T>(s)); }

    template<class T>
    std::basic_string<T> char_class(std::basic_string<T> const &cl) { return cl; }

    std::string space{ "\\s" };
    std::string digit{ "\\d" };
    std::string not_space{ "\\S" };

    std::wstring wspace{ L"\\s" };
    std::wstring wdigit{ L"\\d" };
    std::wstring wnot_digit{ L"\\D" };
};

int main() {

    std::string r{
        match::range('a', 'z') +
        match::literal("XXX") +
        match::char_class(match::space) +
        match::group(
            match::literal("Hello") +
            match::char_class(match::space)) +
        match::any_of("abcdef") +
        match::none_of("qreoi") +
        match::arbno(
            match::range('a','z'))
    };

    std::wstring r2{
        match::range(L'a', L'z') +
        match::literal(L"XXX") +
        match::char_class(match::wspace) +
        match::group(
            match::literal(L"Hello") +
            match::char_class(match::wspace)) +
        match::any_of(L"abcdef") +
        match::none_of(L"qreoi") +
        match::arbno(
            match::range(L'a', L'z'))
    };

    std::cout << r << "\n";
    std::wcout << r2 << L"\n";
}

For the moment, I've just created a string and printed it out (so I could check that I got what I expected), but creating a regex from that is obviously a trivial change.

I'm pretty sure by the time you added the missing operators, the result would still be pretty small compared to (for example) just the traits classes.

Bottom line: I wouldn't say I'm exactly excited about the result, but at least to me the notion of using it qualifies for a hesitant "maybe" instead of "no, absolutely not."

That's especially true if I change the surrounding code just a tad:

using namespace match;

std::string r{
    range('a', 'z') +
    literal("XXX") +
    char_class(space) +
    group(
        literal("Hello") +
        char_class(space)) +
    any_of("abcdef") +
    none_of("qreoi") +
    arbno(
        range('a','z'))
};

I'm still not really excited, but I can say "maybe" with a bit less hesitation.

Edit: I've modified the code somewhat, and added the (implied) support for both narrow and wide characters. For the moment I've had to add overloads for both std::basic_string<T> and T const *. For some reason I don't quite understand, the compiler won't treat the former as the right overload when passing a string literal. Probably just too late at night and my brain has stopped working, but anyway, I guess adding the overloads isn't too heinous (and when somebody is thinking more clearly, maybe they can get rid of those).

Thanks a ton. I did get feedback somewhere else too that it was way too verbose, so I'm definitely going to rework that, and with that make the code smaller. — MivVG
– MivVG, Commented Feb 7, 2019 at 10:48
@MivVG: I was just doing some more editing. Not sure if you like the new version better. It may just be excessive fatigue, but I think I do. — Jerry Coffin
– Jerry Coffin, Commented Feb 7, 2019 at 10:54

Quuxplusone · Accepted Answer · 2019-02-04 21:04:25Z

This looks like a great use-case for a Domain-Specific Language (DSL). If you had a nice compact DSL for representing automata like this, then you could replace all this boilerplate

auto regex = generator.create_regex()
                      .then_match(regex_generator::match_range('a', 'z'))
                      .then_match(regex_generator::match_string("XXX"))
                      .then_match(regex_generator::match_space())
                      .then_match(regex_generator::match_group(
                          generator.create_regex()
                              .then_match(regex_generator::match_string("Hello"))
                              .then_match(regex_generator::match_space())))
                      .then_match(regex_generator::match_any_of("abcdef"))
                      .then_match(regex_generator::match_none_of("qreoi"))
                      .then_match(regex_generator::match_zero_or_more(
                          regex_generator::match_range('a', 'z')));
std::regex regex_obj(regex.str());

with a simple, readable expression. Just spitballing some syntax here; tell me how you like it —

std::regex regex_obj = std::regex(
    "[a-z]XXX\\s(Hello\\s)[abcdef][^qreoi][a-z]*"
);

See how a complicated recipe like generator.create_regex().then_match(regex_generator::match_any_of("abcdef")).then_match(regex_generator::match_none_of("qreoi")) can be written super efficiently as std::regex("[abcdef][^qreoi]")!

Something like this is the motivating force behind Boost.Spirit, although Spirit uses operator overloading and other party tricks to avoid writing the quotation marks. I think you'd like Spirit.

The one downside of my proposed DSL for regular expressions is that I foolishly decided to use \s to represent what you called regex_generator::match_space(). This is unfortunate because C++ already uses \ for something else, and so I ended up having to escape the backslash in my DSL syntax. If I were really feeling adventurous, I might do something like this:

#define RX(...) std::regex(#__VA_ARGS__)

std::regex regex_obj = RX([a-z]XXX\s(Hello\s)[abcdef][^qreoi][a-z]*);

However, I would need to be cautious when splitting such a regex across source lines, or if I wanted to write a regex containing unbalanced parentheses for some reason.

While I appreciate it that you take your time to formulate an opinion on my project, it is not really what I am looking for in a code review. I am looking for specific suggestions to make my code better, not for critique on the use of it. — MivVG
– MivVG, Commented Feb 5, 2019 at 17:58

Stack Exchange Network

Regex Generator in C++

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Regex Generator in C++

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions