cpp2regex.h2

//  Copyright (c) Herb Sutter
//  SPDX-License-Identifier: CC-BY-NC-ND-4.0

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.


//===========================================================================
//  Regex support
//===========================================================================

#ifndef CPP2_CPP2REGEX_H
#define CPP2_CPP2REGEX_H


template<typename matcher_wrapper, typename Iter, typename CharT>
using matcher_wrapper_type = typename matcher_wrapper::template wrap<Iter, CharT>;

template<typename matcher>
using matcher_context_type = typename matcher::context;

using error_func = std::function<void(std::string)>;

cpp2: namespace = {

regex: namespace = {

bview  : <CharT> type == std::basic_string_view<CharT>;
bstring: <CharT> type == std::basic_string<CharT>;


//-----------------------------------------------------------------------
//
//  Helper structures for the expression matching.
//
//-----------------------------------------------------------------------
//

//  Possible modifiers for a regular expression.
//
expression_flags: @flag_enum<u8> type = 
{
    case_insensitive;             // mod: i
    multiple_lines;               // mod: m
    single_line;                  // mod: s
    no_group_captures;            // mod: n
    perl_code_syntax;             // mod: x
    perl_code_syntax_in_classes;  // mod: xx
}

//  Structure for storing group information.
//
match_group: @struct <Iter> type = 
{
    start: Iter = ();
    end: Iter = ();

    matched: bool = false;
}

//  Return value for every matcher.
// 
match_return: @struct <Iter> type = 
{
    matched: bool = false;
    pos: Iter = ();
}

//  Modifiable state during matching.
//
match_context: <CharT, Iter, max_groups: int> type =
{
    public  begin : Iter;
    public  end   : Iter;

    private groups: std::array<match_group<Iter>, max_groups> = ();

    operator=: (out this, begin_: Iter, end_: Iter) = {
        begin = begin_;
        end = end_;
    }

    operator=: (out this, that) = {}

    //  Getter and setter for groups
    //
    get_group: (in this, group) groups[group];

    get_group_end:    (in this, group) -> int = {
        if group >= max_groups || !groups[group].matched {
            return 0;
        }
        return cpp2::unsafe_narrow<int>( std::distance(begin, groups[group].end) );
    }
    get_group_start:  (in this, group) -> int = {
        if group >= max_groups || !groups[group].matched {
            return 0;
        }
        return cpp2::unsafe_narrow<int>( std::distance(begin, groups[group].start) );
    }
    get_group_string: (in this, group) -> std::string = {
        if group >= max_groups || !groups[group].matched {
            return "";
        }
        return std::string(groups[group].start, groups[group].end);
    }
    
    set_group_end: (inout this, group, pos) = {
        groups[group].end = pos;
        groups[group].matched = true;
    }

    set_group_invalid: (inout this, group) = {
        groups[group].matched = false;
    }

    set_group_start: (inout this, group, pos) = {
        groups[group].start = pos;
    }

    size: (in this) max_groups;

    //  Misc functions
    //
    fail: (in this)            match_return<Iter>(false, end);
    pass: (in this, cur: Iter) match_return<Iter>(true, cur);
}


//  End function that returns a valid match.
//
true_end_func: @struct type = 
{
    operator(): (in this, cur, inout ctx) ctx..pass(cur);
}


//  Empty group reset function.
//
no_reset: @struct type = 
{
    operator(): (this, inout _:) = {}
}


//  Evaluate func on destruction of the handle.
on_return: <Func> type = 
{
    func: Func;

    operator=: (out this, f: Func) = {
        func = f;
    }

    operator=: (move this) = {
        func();
    }
}


//  Helper for auto deduction of the Func type.
make_on_return: <Func> (func: Func) on_return<Func>(func);


//-----------------------------------------------------------------------
//
//  Character classes for regular expressions.
//
//-----------------------------------------------------------------------
//

//  Class syntax: <any character> Example: a
//
single_class_entry: <CharT, C: CharT> type =
{
    includes : (c: CharT) c == C;
    to_string: ()         bstring<CharT>(1, C);
}


//  Class syntax: - Example: a-c
//
range_class_entry: <CharT, Start: CharT, End: CharT> type =
{
    includes : (c: CharT) Start <= c <= End;
    to_string: ()         "(Start)$-(End)$";
}


//  Helper for combining two character classes
//
combined_class_entry: <CharT, List ...> type = 
{
    includes : (c: CharT) (false || ... || List::includes(c));
    to_string: ()         (bstring<CharT>() + ... + List::to_string());
}


//  Class syntax: <list of characters>  Example: abcd
//
list_class_entry: <CharT, List ... : CharT> type = 
{
    includes : (c: CharT) (false || ... || (List == c));
    to_string: ()         (bstring<CharT>() + ... + List);
}


//  Class syntax: [:<class name:]  Example: [:alnum:]
//
named_class_entry: <CharT, Name: string_util::fixed_string, Inner> type = 
{
    includes : (c: CharT) Inner::includes(c);
    to_string: ()         "[:(Name..data())$:]";
}


negated_class_entry: <CharT, Inner> type = 
{
    this    : Inner      = ();
    includes: (c: CharT) !Inner::includes(c);
}


//  Short class syntax: \<character>  Example: \w
//
shorthand_class_entry: <CharT, Name: string_util::fixed_string, Inner> type = 
{
    includes : (c: CharT) Inner::includes(c);
    to_string: ()         Name..str();
}


//  Named basic character classes
//
digits_class  : <CharT> type == named_class_entry<CharT, "digits", range_class_entry<CharT, '0', '9'>>;
lower_class   : <CharT> type == named_class_entry<CharT, "lower",  range_class_entry<CharT, 'a', 'z'>>;
upper_class   : <CharT> type == named_class_entry<CharT, "upper",  range_class_entry<CharT, 'A', 'Z'>>;

//  Named other classes
//
alnum_class     : <CharT> type == named_class_entry<CharT, "alnum",  combined_class_entry<CharT, lower_class<CharT>, upper_class<CharT>, digits_class<CharT>>>;
alpha_class     : <CharT> type == named_class_entry<CharT, "alpha",  combined_class_entry<CharT, lower_class<CharT>, upper_class<CharT>>>;
ascii_class     : <CharT> type == named_class_entry<CharT, "ascii",  range_class_entry<CharT, '\x00', '\x7F'>>;
blank_class     : <CharT> type == named_class_entry<CharT, "blank",  list_class_entry<CharT, ' ', '\t'>>;
cntrl_class     : <CharT> type == named_class_entry<CharT, "cntrl",  combined_class_entry<CharT, range_class_entry<CharT, '\x00', '\x1F'>, single_class_entry<CharT, '\x7F'>>>;
graph_class     : <CharT> type == named_class_entry<CharT, "graph",  range_class_entry<CharT, '\x21', '\x7E'>>;
hor_space_class : <CharT> type == named_class_entry<CharT, "hspace", list_class_entry<CharT, '\t', ' '>>;
print_class     : <CharT> type == named_class_entry<CharT, "print",  range_class_entry<CharT, '\x20', '\x7E'>>;
punct_class     : <CharT> type == named_class_entry<CharT, "punct",  list_class_entry<CharT, '[','!','"','#','$','%','&','\'','(',')','*','+',',','-','.','/',':',';','<','=','>','?','@','[','\\',']','^','_','`','{','|','}','~',']'>>;
space_class     : <CharT> type == named_class_entry<CharT, "space",  list_class_entry<CharT, ' ', '\t', '\r', '\n', '\v', '\f'>>;
ver_space_class : <CharT> type == named_class_entry<CharT, "vspace", list_class_entry<CharT, '\n', '\v', '\f', '\r'>>;
word_class      : <CharT> type == named_class_entry<CharT, "word",   combined_class_entry<CharT, alnum_class<CharT>, single_class_entry<CharT, '_'>>>;
xdigit_class    : <CharT> type == named_class_entry<CharT, "xdigit", combined_class_entry<CharT, range_class_entry<CharT, 'A', 'F'>, range_class_entry<CharT, 'a', 'f'>, digits_class<CharT>>>;

// Shorthand class entries
//
short_digits_class     : <CharT> type == shorthand_class_entry<CharT, "\\d", digits_class<CharT>>;
short_hor_space_class  : <CharT> type == shorthand_class_entry<CharT, "\\h", hor_space_class<CharT>>;
short_space_class      : <CharT> type == shorthand_class_entry<CharT, "\\s", space_class<CharT>>;
short_vert_space_class : <CharT> type == shorthand_class_entry<CharT, "\\v", ver_space_class<CharT>>;
short_word_class       : <CharT> type == shorthand_class_entry<CharT, "\\w", word_class<CharT>>;

short_not_digits_class     : <CharT> type == negated_class_entry<CharT, shorthand_class_entry<CharT, "\\D", digits_class<CharT>>>;
short_not_hor_space_class  : <CharT> type == negated_class_entry<CharT, shorthand_class_entry<CharT, "\\H", hor_space_class<CharT>>>;
short_not_space_class      : <CharT> type == negated_class_entry<CharT, shorthand_class_entry<CharT, "\\S", space_class<CharT>>>;
short_not_vert_space_class : <CharT> type == negated_class_entry<CharT, shorthand_class_entry<CharT, "\\V", ver_space_class<CharT>>>;
short_not_word_class       : <CharT> type == negated_class_entry<CharT, shorthand_class_entry<CharT, "\\W", word_class<CharT>>>;


//-----------------------------------------------------------------------
//
//  Tokens for regular expressions.
//
//-----------------------------------------------------------------------
//

// Basic class for a regex token.
//
regex_token: @polymorphic_base type = 
{
    public string_rep: std::string;

    operator=:(out this, str: std::string) = {
        string_rep = str;
    }

    operator=:(out this) = {
        string_rep = "";
    }

    //parse: (inout ctx: parse_context) -> token_ptr;
    generate_code: (virtual this, inout _: generation_context);        // Generate the matching code.

    add_groups: (virtual this, inout _: std::set<int>) = {}            // Adds all group indices to the set.
    to_string: (this) -> std::string         = { return string_rep; }  // Create a string representation.
    set_string: (inout this, s: std::string) = { string_rep = s; }     // Set the string representation.
}

token_ptr : type == std::shared_ptr<regex_token>;
token_vec: type == std::vector<token_ptr>;


//  Adds a check in code generation.
//
regex_token_check: @polymorphic_base type = 
{
    this: regex_token;

    check: std::string;

    operator=:(out this, str: std::string, check_: std::string) = {
        regex_token = (str);
        check = check_;
    }

    generate_code: (override this, inout ctx: generation_context) = {
        ctx..add_check(check + "(" + ctx..match_parameters() + ")");
    }
}


//  Adds code in code generation.
//
regex_token_code: @polymorphic_base type = 
{
    this: regex_token;

    code: std::string;

    operator=:(out this, str: std::string, code_: std::string) = {
        regex_token = (str);
        code = code_;
    }

    generate_code: (override this, inout ctx: generation_context) = {
        ctx..add(code);
    }
}


//  Token that does not influence the matching. E.g. comment.
//
regex_token_empty: @polymorphic_base type = 
{
    this: regex_token;

    operator=:(out this, str: std::string) = {
        regex_token = (str);
    }

    generate_code: (override this, inout _: generation_context) = {
        // Nothing.
    }
}


//  Represents a list of regex tokens as one token.
//
regex_token_list: @polymorphic_base type = 
{
    this: regex_token;

    public tokens: token_vec;

    operator=:(out this, t: token_vec) = {
        regex_token = (gen_string(t));
        tokens = t;
    }

    generate_code: (override this, inout ctx: generation_context) = {
        for tokens do (token) {
            token*..generate_code(ctx);
        }
    }

    add_groups: (override this, inout groups: std::set<int>) = {
        for tokens do (token) {
            token*..add_groups(groups);
        }
    }

    gen_string: (vec: token_vec) -> std::string = {
        r : std::string = "";
        for vec do (token) {
            r += token*..to_string();
        }
        return r;
    }
}


//-----------------------------------------------------------------------
//
//  Parse and generation context.
//
//-----------------------------------------------------------------------
//

//  State of the current capturing group. See '(<pattern>)'
//
parse_context_group_state: @struct type = 
{    
    cur_match_list:        token_vec = ();         // Current list of matchers.
    alternate_match_lists: token_vec = ();         // List of alternate matcher lists. E.g. ab|cd|xy.
    modifiers :            expression_flags = ();  // Current modifiers for the group/regular expression.

    //  Start a new alternative.
    next_alternative: (inout this) = {
        new_list: token_vec = ();
        std::swap(new_list, cur_match_list);
        post_process_list(new_list);
        _ = alternate_match_lists..insert(alternate_match_lists..end(), shared.new<regex_token_list>(new_list));
    }

    //  Swap this state with the other one.
    swap: (inout this, inout t: parse_context_group_state) = {
        std::swap(cur_match_list, t.cur_match_list);
        std::swap(alternate_match_lists, t.alternate_match_lists);
        std::swap(modifiers, t.modifiers);
    }

    //  Convert this state into a regex token.
    get_as_token: (inout this) -> token_ptr = {
        if alternate_match_lists..empty() {
            post_process_list(cur_match_list);
            return shared.new<regex_token_list>(cur_match_list);
        }
        else {
            next_alternative();
            return shared.new<alternative_token_gen>(alternate_match_lists);
        }
    }

    //  Add a token to the current matcher list.
    add: (inout this, token: token_ptr) = {
        cur_match_list..push_back(token);
    }

    //  True if current matcher list is empty.
    empty: (this) -> bool = cur_match_list..empty();

    
    //  Apply optimizations to the matcher list.
    post_process_list: (inout list: token_vec) = {
        // Merge all characters
        merge_pos := list..begin();
        while merge_pos != list..end() next (merge_pos++) {
            if merge_pos** is char_token {
                combine_pos := merge_pos + 1;
                while combine_pos != list..end() && combine_pos** is char_token { // The erase advances combine_pos
                    (merge_pos** as char_token)..append(combine_pos** as char_token);
                    combine_pos = list..erase(combine_pos);
                }
            }
        }
    }
}


//  State for the branch reset. Takes care of the group numbering. See '(|<pattern>)'.
//
parse_context_branch_reset_state: @struct type = 
{
    is_active : bool = false; // If we have a branch reset group.
    cur_group : int  = 1;     // Next group identifier. 0 == global capture group.
    max_group : int  = 1;     // Maximum group identifier generated.
    from      : int  = 1;     // Starting identifier on new alternative branch.

    //  Next group identifier.
    next: (inout this) -> int = {
        g := cur_group;
        cur_group += 1;
        max_group = max(max_group, cur_group);

        return g;
    }

    //  Set next group identifier.
    set_next: (inout this, g: int) = {
        cur_group = g;
        max_group = max(max_group, g);
    }

    //  Start a new alternative branch.
    next_alternative: (inout this) = {
        if is_active {
            cur_group = from;
        }
    }

    //  Initialize for a branch reset group.
    set_active_reset: (inout this, restart: int) = {
        is_active = true;
        cur_group = restart;
        from      = restart;
        max_group = restart;
    }
}


//  Context during parsing of the regular expressions.
// 
//  Keeps track of the distributed group identifiers, current parsed group and branch resets.
//
parse_context: type = 
{
    regex: std::string_view;   // Regular expression string.
    pos:   size_t = 0;         // Current parsing position.
    root:  token_ptr;          // Token representing the regular expression.

    cur_group_state:        parse_context_group_state = ();
    cur_branch_reset_state: parse_context_branch_reset_state = ();

    
    public named_groups:  std::map<std::string, int> = ();

    error_out: error_func; // TODO: Declaring std::function<void(std::string)> fails for cpp2.
    has_error: bool      = false;

    operator=:(out this, r: std::string_view, e) = {
        regex = r;
        root = shared.new<regex_token_empty>("");
        error_out = e;
    }

    //  State management functions
    //

    //  Returned group state needs to be stored and provided in `end_group`.
    start_group: (inout this) -> parse_context_group_state = 
    {
        old_state: parse_context_group_state = ();
        old_state..swap(cur_group_state);
        cur_group_state.modifiers = old_state.modifiers;

        return old_state;
    }

    //  `old_state` argument needs to be from start group.
    end_group: (inout this, old_state: parse_context_group_state) -> token_ptr =
    {
        inner := cur_group_state..get_as_token();
        cur_group_state = old_state;
        return inner;
    }

    get_modifiers: (this) -> expression_flags = {
        return cur_group_state.modifiers;
    }

    set_modifiers: (inout this, mod: expression_flags) = {
        cur_group_state.modifiers = mod;
    }

    //  Branch reset management functions
    //

    branch_reset_new_state: (inout this) -> parse_context_branch_reset_state = 
    {
        old_state: parse_context_branch_reset_state = ();
        std::swap(old_state, cur_branch_reset_state);

        cur_branch_reset_state..set_active_reset(old_state.cur_group);
        return old_state;
    }

    branch_reset_restore_state: (inout this, old_state: parse_context_branch_reset_state) = 
    {
        max_group := cur_branch_reset_state.max_group;
        cur_branch_reset_state = old_state;
        cur_branch_reset_state..set_next(max_group);
    }

    next_alternative: (inout this) = 
    {
        cur_group_state..next_alternative();
        cur_branch_reset_state..next_alternative();
    }

    //  Regex token management
    //
    add_token: (inout this, token: token_ptr) = {
        cur_group_state..add(token);
    }

    has_token: (this) -> bool = {
        return !cur_group_state..empty();
    }

    pop_token: (inout this) -> token_ptr = 
    {
        r : token_ptr = nullptr;
        if has_token() {
            r = cur_group_state.cur_match_list..back();
            cur_group_state.cur_match_list..pop_back();
        }

        return r;
    }

    get_as_token: (inout this) -> token_ptr = {
        return root;
    }

    //  Group management
    //
    get_cur_group: (this) -> int = {
        return cur_branch_reset_state.cur_group;
    }

    next_group: (inout this) -> int = {
        return cur_branch_reset_state..next();
    }

    set_named_group: (inout this, name: std::string, id: int) = 
    {
        if !named_groups..contains(name) { // Redefinition of group name is not an error. The left most one is retained.
            named_groups[name] = id;
        }
    }

    get_named_group: (this, name: std::string) -> int = 
    {
        iter := named_groups..find(name);
        if iter == named_groups..end() {
             return -1;
        }
        else {
            return iter*.second;
        }
    }
    
    //  Position management functions
    //
    current: (this) -> char = { return regex[pos]; }

    //  Get the next token in the regex, skipping spaces according to the parameters. See `x` and `xx` modifiers.
    private get_next_position: (in this, in_class: bool, no_skip: bool) -> size_t = 
    {
        perl_syntax := false;
        if !no_skip {
            if in_class {
                perl_syntax = get_modifiers()..has(expression_flags::perl_code_syntax) && get_modifiers()..has(expression_flags::perl_code_syntax_in_classes);
            }
            else {
                perl_syntax = get_modifiers()..has(expression_flags::perl_code_syntax);
            }
        }
        cur := pos + 1;
        if perl_syntax {
            while cur < regex..size() next (cur += 1) {
                n: = regex[cur];

                if space_class<char>::includes(n) {
                    continue;
                }
                else if !in_class && '#' == n {
                    cur = regex..find("\n", cur);
                    if std::string::npos == cur {
                        // No new line, comment runs until the end of the pattern
                        cur = regex..size();
                    }
                }
                else { // None space none comment char
                    break;
                }
            }
        }

        //  Check for end of file.
        if cur > regex..size() {
            cur = regex..size();
        }
        return cur;
    }

    //  Return true if next token is available.
    private next_impl: (inout this, in_class: bool, no_skip: bool) -> bool = 
    {
        pos = get_next_position(in_class, no_skip);
        if pos != regex..size() {
            return true;
        }
        else {
            return false;
        }
    }

    next         : (inout this) next_impl(false, false);
    next_in_class: (inout this) next_impl( true, false);
    next_no_skip : (inout this) next_impl(false,  true);

    next_n: (inout this, n: int) -> bool = {
        r := true;
        cur := 0;
        while r && cur < n next (r = next()) {
            cur += 1;
        }
        return r;
    }

    has_next: (this) -> bool = { return pos < regex..size(); }

    private grab_until_impl: (inout this, in e: std::string, out r: std::string, any: bool) -> bool = 
    {
        end:= pos;
        if any {
            end = regex..find_first_of(e, pos);
        }
        else {
            end = regex..find(e, pos);
        }

        if end != std::string_view::npos {
            r = regex..substr(pos, end - pos);
            pos = end;
            return true;
        }
        else {
            r = "";
            return false;
        }
    }

    grab_until: (inout this, in e: std::string, out r: std::string)        grab_until_impl(e, out r, false);
    grab_until: (inout this, in e: char, out r: std::string)               grab_until_impl(std::string(1, e), out r, false);
    grab_until_one_of: (inout this, in e: std::string, out r: std::string) grab_until_impl(e, out r, true);

    grab_n: (inout this, in n: int, out r: std::string) -> bool = 
    {
        if pos + n <= regex..size() {
            r = regex..substr(pos, n);
            pos += n - 1;
            return true;
        }
        else {
            r = "";
            return false;
        }
    }

    grab_number: (inout this) -> std::string = 
    {
        start := pos;
        start_search := pos;
        if regex[start_search] == '-' {
            start_search += 1;
        }
        end := regex..find_first_not_of("1234567890", start_search);

        r : std::string;
        if end != std::string::npos {
            r = regex..substr(start, end - start);
            pos = end - 1;
        }
        else {
            r = regex..substr(start);
            pos = regex..size() - 1;
        }
        return r;
    }

    private peek_impl: (in this, in_class: bool) -> char = {
        next_pos := get_next_position(in_class, false);
        if next_pos < regex..size() {
            return regex[next_pos];
        }
        else {
            return '\0';
        }
    }

    peek         : (in this) peek_impl(false);
    peek_in_class: (in this) peek_impl( true);


    //  Parsing functions
    //
    parser_group_modifiers: (inout this, change_str: std::string, inout parser_modifiers: expression_flags) -> bool = 
    {
        is_negative := false;
        is_reset    := false;

        apply := :(flag: expression_flags) = {
            if is_negative&$* {
                parser_modifiers&$*..clear(flag);
            }
            else {
                parser_modifiers&$*..set(flag);
            }
        };

        iter := change_str..begin();
        while iter != change_str..end() next (iter++) 
        {
            cur := iter*;
            if cur == '^' {
                is_reset = true;
                parser_modifiers = expression_flags::none;
            }
            else if cur == '-' {
                if is_reset { _= error("No negative modifier allowed."); return false; }
                is_negative = true;
            }
            else if cur == 'i' { apply(expression_flags::case_insensitive); }
            else if cur == 'm' { apply(expression_flags::multiple_lines); }
            else if cur == 's' { apply(expression_flags::single_line); }
            else if cur == 'n' { apply(expression_flags::no_group_captures); }
            else if cur == 'x' {
                if (iter + 1) == change_str..end() || (iter + 1)* != 'x' {
                    // x modifier
                    apply(expression_flags::perl_code_syntax);

                    // Just x unsets xx and remove x also removes xx
                    parser_modifiers..clear(expression_flags::perl_code_syntax_in_classes);
                }
                else { // xx modifier
                    // xx also sets or unsets x
                    apply(expression_flags::perl_code_syntax);
                    apply(expression_flags::perl_code_syntax_in_classes);

                    iter++; // Skip the second x
                }
            }
            else {
                _= error("Unknown modifier: (cur)$"); return false;
            }
        }

        return true;
    }

    parse_until:(inout this, term: char) -> bool = {
        cur_token: token_ptr = ();

        while valid() next _ = next()
        {
            if term == current() { break; }

            cur_token = nullptr;

            if !cur_token && valid() { cur_token = alternative_token::parse(this); }
            if !cur_token && valid() { cur_token = any_token::parse(this); }
            if !cur_token && valid() { cur_token = class_token::parse(this); }
            if !cur_token && valid() { cur_token = escape_token_parse(this); }
            if !cur_token && valid() { cur_token = global_group_reset_token_parse(this); }
            if !cur_token && valid() { cur_token = group_ref_token::parse(this); }
            if !cur_token && valid() { cur_token = group_token::parse(this); }
            if !cur_token && valid() { cur_token = hexadecimal_token_parse(this); }
            if !cur_token && valid() { cur_token = line_end_token_parse(this); }
            if !cur_token && valid() { cur_token = line_start_token_parse(this); }
            if !cur_token && valid() { cur_token = named_class_token_parse(this); }
            if !cur_token && valid() { cur_token = octal_token_parse(this); }
            if !cur_token && valid() { cur_token = range_token::parse(this); }
            if !cur_token && valid() { cur_token = special_range_token::parse(this); }
            if !cur_token && valid() { cur_token = word_boundary_token_parse(this); }

            // Everything else is matched as it is.
            if !cur_token && valid() { cur_token = char_token::parse(this); }

            if cur_token && valid() {
                add_token(cur_token);
            } else {
                return false;
            }
        }

        return true;
    }

    parse: (inout this, modifiers: std::string) -> bool = 
    {

        flags : expression_flags = ();
        if !parser_group_modifiers(modifiers, flags) { return false; }
        set_modifiers(flags);

        r := parse_until('\0');
        if r {
            root = cur_group_state..get_as_token();
        }

        return r;
    }

    //  Misc functions

    get_pos:   (this)                             pos;
    get_range: (this, start: size_t, end: size_t) std::string(regex..substr(start, end - start + 1));
    valid:     (this) -> bool                   = { return has_next() && !has_error; }

    error: (inout this, err: std::string) -> token_ptr = {
        has_error = true;
        error_out("Error during parsing of regex '(regex)$' at position '(pos)$': (err)$");
        return nullptr;
    }
}


//  Context for one function generation. Generation of functions can be interleaved,
//  therefore we buffer the code for one function here.
//
generation_function_context: @struct type = {
    code: std::string = "";
    tabs: std::string = "";

    add_tabs: (inout this, c: int) = {
        i: int = 0;
        while i < c next i += 1 {
            tabs += "  ";
        }
    }

    remove_tabs: (inout this, c: int) = {
        tabs = tabs..substr(0, c * 2);
    }
}


//  Context for generating the state machine.
generation_context: type = 
{
    gen_stack: std::vector<generation_function_context> = (1); // Element 0 contains all the code.

    matcher_func: int         = 0;
    reset_func:   int         = 0;
    temp_name:    int         = 0;
    entry_func:   std::string = "";

    //  Generation helpers
    //
    match_parameters: (this) -> std::string = { return "r.pos, ctx"; }

    //  Code generation.

    //  Add code line.
    add: (inout this, s: std::string) = {
        cur := get_current();
        cur*.code += "(cur*.tabs)$(s)$\n";
    }

    //  Add check for token. The check needs to be a function call that returns a boolean.
    add_check: (inout this, check: std::string) = {
        cur := get_current();
        cur*.code += "(cur*.tabs)$if !cpp2::regex::(check)$ { r.matched = false; break; }\n";
    }

    //  Add a stateful check. The check needs to return a `match_return`.
    add_statefull: (inout this, next_func: std::string, check: std::string) = 
    {
        end_func_statefull(check);

        name := next_func..substr(0, next_func..size() - 2);
        start_func_named(name);
    }

    protected start_func_named: (inout this, name: std::string) = 
    {
        cur := new_context();

        cur*.code += "(cur*.tabs)$(name)$: @struct type = {\n";
        cur*.code += "(cur*.tabs)$  operator(): (this, cur: Iter, inout ctx: context, other) -> cpp2::regex::match_return<Iter> = {\n";
        cur*.code += "(cur*.tabs)$    r := ctx..pass(cur);\n";
        cur*.code += "(cur*.tabs)$    do {\n";
        cur*..add_tabs(3);
    }

    protected start_func: (inout this) -> std::string = 
    {
        name := gen_func_name();
        start_func_named(name);
        return name + "()";
    }

    protected end_func_statefull: (inout this, s: std::string) = 
    {
        cur := get_current();
        cur*..remove_tabs(3);
        cur*.code += "\n";
        cur*.code += "(cur*.tabs)$    } while false;\n";
        cur*.code += "(cur*.tabs)$    if r.matched {\n";
        cur*.code += "(cur*.tabs)$      r = (s)$;\n";
        cur*.code += "(cur*.tabs)$    }\n";
        cur*.code += "(cur*.tabs)$    else {\n";
        cur*.code += "(cur*.tabs)$      r.pos = ctx.end;\n";
        cur*.code += "(cur*.tabs)$    }\n";
        cur*.code += "(cur*.tabs)$    return r;\n";
        cur*.code += "(cur*.tabs)$  }\n";
        cur*.code += "(cur*.tabs)$}\n";

        finish_context();
    }

    //  Generate the function for a token.
    generate_func: (inout this, token: token_ptr) -> std::string = 
    {
        name := start_func();
        token*..generate_code(this);
        end_func_statefull("other((match_parameters())$)");

        return name;
    }

    //  Generate the reset for a list of group identifiers.
    generate_reset: (inout this, groups: std::set<int>) -> std::string = 
    {
        if groups..empty() {
            return "cpp2::regex::no_reset()";
        }

        name := gen_reset_func_name();
        cur := new_context();

        cur*.code += "(cur*.tabs)$(name)$: @struct type = {\n";
        cur*.code += "(cur*.tabs)$  operator(): (this, inout ctx) = {\n";
        for groups do (g) {
            cur*.code += "(cur*.tabs)$  ctx..set_group_invalid((g)$);\n";
        }
        cur*.code += "(cur*.tabs)$  }\n";
        cur*.code += "(cur*.tabs)$}\n";

        finish_context();

        return name + "()";
    }

    //  Name generation
    //
    protected gen_func_name: (inout this) -> std::string = {
        cur_id : = matcher_func;
        matcher_func += 1;
        return "func_(cur_id)$";
    }

    next_func_name: (inout this) -> std::string = {
        return gen_func_name() + "()";
    }

    protected gen_reset_func_name: (inout this) -> std::string = {
        cur_id : = reset_func;
        reset_func += 1;
        return "reset_(cur_id)$";
    }

    gen_temp: (inout this) -> std::string = {
        cur_id := temp_name;
        temp_name += 1;
        return "tmp_(cur_id)$";
    }

    //  Context management
    //
    new_context: (inout this) -> *generation_function_context = {
        gen_stack..push_back(generation_function_context());
        cur := get_current();
        cur*.tabs = "    ";

        return cur;
    }

    finish_context: (inout this) = {
        cur := get_current();
        base := get_base();
        base*.code += cur*.code;

        gen_stack..pop_back();
    }

    //  Misc functions
    //
    private get_current: (inout this) -> *generation_function_context = {
        return gen_stack..back()&;
    }

    private get_base: (inout this) -> *generation_function_context = {
        return gen_stack[0]&;
    }

    get_entry_func: (this) -> std::string = {
        return entry_func;
    }

    create_named_group_lookup: (this, named_groups: std::map<std::string, int>) -> std::string = 
    {
        res: std::string = "get_named_group_index: (name) -> int = {\n";

        //  Generate if selection.
        sep: std::string = "";
        for named_groups do (cur) {
            res += "(sep)$if name == \"(cur.first)$\" { return (cur.second)$; }";
            sep = "else ";
        }

        //  Generate else branch or return if list is empty.
        if named_groups..empty() {
            res += "  _ = name;\n";
            res += "  return -1;\n";
        }
        else {
            res += "  else { return -1; }\n";
        }
        res += "}\n";
        return res;
    }


    //  Run the generation for the token.
    run: (inout this, token: token_ptr) -> std::string = {
        entry_func = generate_func(token);

        return get_base()*.code;
    }
}


//  Regex syntax: |  Example: ab|ba
//
//  Non greedy implementation. First alternative that matches is chosen.
//
alternative_token: @polymorphic_base type = 
{
    this: regex_token_empty = ("");  // No code gen here. alternative_token_gen is created in the parse_context

    operator=:(out this) = {}

    parse: (inout ctx: parse_context) -> token_ptr = {
        if ctx..current() != '|' { return nullptr; }

        if !ctx..has_token() { return ctx..error("Alternative with no content."); }
        ctx..next_alternative();
        return shared.new<alternative_token>();
    }
}

alternative_token_gen: @polymorphic_base type = 
{
    this: regex_token;

    alternatives: token_vec;

    operator=: (out this, a: token_vec) = {
        regex_token = gen_string(a);
        alternatives = a;
    }

    generate_code: (override this, inout ctx: generation_context) = 
    {
        functions: std::string = "";

        for alternatives do (cur) {
            groups: std::set<int> = ();
            cur*..add_groups(groups);

            functions += ", " + ctx..generate_func(cur);
            functions += ", " + ctx..generate_reset(groups);
        }

        next_name := ctx..next_func_name();

        ctx..add_statefull(next_name, "cpp2::regex::alternative_token_matcher<char>::match((ctx..match_parameters())$, other, (next_name)$ (functions)$)");
    }

    add_groups: (override this, inout groups: std::set<int>) = 
    {
        for alternatives do (cur) {
            cur*..add_groups(groups);
        }
    }

    gen_string: (a: token_vec) -> std::string = 
    {
        r: std::string = "";
        sep: std::string = "";

        for a do (cur) {
            r += sep + cur*..to_string();
            sep = "|";
        }

        return r;
    }
}


alternative_token_matcher: <CharT> type = 
{
    match: (cur, inout ctx, end_func, tail, functions ...) -> _ = {
        return match_first(cur, ctx, end_func, tail, functions...);
    }

    private match_first: <Other ...> (cur, inout ctx, end_func, tail, cur_func, cur_reset, other ...: Other) -> _ = 
    {
        inner_call := :(tail_cur, inout tail_ctx) -> _ == {
            return (tail)$(tail_cur, tail_ctx, (end_func)$);
        };
        r := cur_func(cur, ctx, inner_call);
        if r.matched {
            return r;
        } else {
            cur_reset(ctx);

            if constexpr 0 != sizeof...(Other) {
                return match_first(cur, ctx, end_func, tail, other...);
            } else {
                return ctx..fail();
            }
        }
    }
}


//  Regex syntax: .
//
any_token: @polymorphic_base type = 
{
    this: regex_token_check = (".");

    operator=:(out this, single_line: bool) = {
        regex_token_check = (".", "any_token_matcher<char, (single_line)$>");
    }

    parse: (inout ctx: parse_context) -> token_ptr = {
        if '.' != ctx..current() { return nullptr;}

        return shared.new<any_token>(ctx..get_modifiers()..has(expression_flags::single_line));
    }
}


any_token_matcher: <CharT, single_line: bool> (inout cur, inout ctx) -> bool = 
{
    if  cur != ctx.end                      // any char except the end
        && (single_line || cur* != '\n')    // do not match new lines in multi line mode
    {
        cur += 1;
        return true;
    }
    //  Else
    return false;
}


//  Regex syntax: a
//
char_token: @polymorphic_base type = 
{
    this: regex_token;

    token      : std::string;
    ignore_case: bool;

    operator=: (out this, t: char, ignore_case_: bool) = {
        regex_token = (std::string(1, t));
        token = t;
        ignore_case = ignore_case_;
    }

    parse: (inout ctx: parse_context) -> token_ptr = {
        return shared.new<char_token>(ctx..current(), ctx..get_modifiers()..has(expression_flags::case_insensitive));
    }

    generate_code: (override this, inout ctx: generation_context) = 
    {
        if ignore_case {
            upper: std::string = token;
            lower: std::string = token;

            (copy i: size_t = 0) while i < token..size() next i += 1 {
                lower[i] = string_util::safe_tolower(token[i]);
                upper[i] = string_util::safe_toupper(token[i]);
            }

            if upper != lower {
                gen_case_insensitive(lower, upper, ctx);
            }
            else {
                gen_case_sensitive(ctx);
            }
        }
        else {
            gen_case_sensitive(ctx);
        }
    }

    gen_case_insensitive: (this, lower: std::string, upper: std::string, inout ctx: generation_context) = 
    {
        name: std::string = "str_(ctx..gen_temp())$";
        lower_name: std::string = "lower_(name)$";
        upper_name: std::string = "upper_(name)$";
        size := token..size();
        ctx..add("(lower_name)$ : std::array<char, (size)$ + 1> = \"(add_escapes(lower))$\";"); // TODO: Add constexpr when Issue https://github.com/hsutter/cppfront/issues/1104 is resolved.
        ctx..add("(upper_name)$ : std::array<char, (size)$ + 1> = \"(add_escapes(upper))$\";"); // TODO: Add constexpr when Issue https://github.com/hsutter/cppfront/issues/1104 is resolved.
        ctx..add("if std::distance(r.pos, ctx.end) < (size)$ {");
        ctx..add("    r.matched = false;");
        ctx..add("    break;");
        ctx..add("}");
        ctx..add("");
        ctx..add("(copy i : int = 0) while i < (size)$ next (i += 1) {");
        ctx..add("    if !((lower_name)$[i] == r.pos[i] || (upper_name)$[i] == r.pos[i]) { r.matched = false; }");
        ctx..add("}");
        ctx..add("");
        ctx..add("if r.matched { r.pos += (size)$; }");
        ctx..add("else { break; }");
    }

    gen_case_sensitive: (this, inout ctx: generation_context) = 
    {
        name: std::string = "str_(ctx..gen_temp())$";
        size := token..size();
        ctx..add("(name)$ : std::array<char, (size)$ + 1> = \"(add_escapes(token))$\";"); // TODO: Add constexpr when Issue https://github.com/hsutter/cppfront/issues/1104 is resolved.
        ctx..add("if std::distance(r.pos, ctx.end) < (size)$ {");
        ctx..add("    r.matched = false;");
        ctx..add("    break;");
        ctx..add("}");
        ctx..add("");
        ctx..add("(copy i : int = 0) while i < (size)$ next (i += 1) {");
        ctx..add("    if (name)$[i] != r.pos[i] { r.matched = false; }");
        ctx..add("}");
        ctx..add("");
        ctx..add("if r.matched { r.pos += (size)$; }");
        ctx..add("else { break; }");
    }

    add_escapes: (this, copy str: std::string) -> std::string = 
    {
        str = string_util::replace_all(str, "\\", "\\\\");
        str = string_util::replace_all(str, "\a", "\\a");
        str = string_util::replace_all(str, "\f", "\\f");
        str = string_util::replace_all(str, "\x1b", "\" \"\\x1b\" \""); // Generate a separated string. This prevents
                                                                        // situations like `\x1bblub` from generating
                                                                        // wrong hex characters.
        str = string_util::replace_all(str, "\n", "\\n");
        str = string_util::replace_all(str, "\r", "\\r");
        str = string_util::replace_all(str, "\t", "\\t");

        return str;
    }

    append: (inout this, that) = {
        this.token += that.token;
        this.string_rep += that.string_rep;
    }
}


// TODO: Check if vectorization works at some point with this implementation.
// char_token_matcher: <tokens: string_util::fixed_string> (inout cur, inout ctx) -> bool = {
//     if !(std::distance(cur, ctx.end) < tokens..size()) {
//         return false;
//     }
//     matched : bool = true;
//     (copy i: int = 0) while i < tokens..size() next i += 1 {
//         if tokens..data()[i] != cur[i] {
//             matched = false; // No break for performance optimization. Without break, the loop vectorizes.
//         }
//     }
//     if matched {
//         cur += tokens..size();
//     }
//     return matched;
// }

// char_token_case_insensitive_matcher: <lower: string_util::fixed_string, upper: string_util::fixed_string> (inout cur, inout ctx) -> bool = {
//     if !(std::distance(cur, ctx.end) < lower..size()) {
//         return false;
//     }
//     matched : bool = true;
//     (copy i : int = 0) while i < lower..size() next i += 1 {
//         if !(lower..data()[i] == cur[i] || upper..data()[i] == cur[i]) {
//             matched = false; // No break for performance optimization. Without break, the loop vectorizes.
//         }
//     }
//     if matched {
//         cur += lower..size();
//     }
//     return matched;
// }


//  Regex syntax: [<character classes>]  Example: [abcx-y[:digits:]]
//
class_token: @polymorphic_base type = 
{
    this            : regex_token = ();

    negate          : bool;
    case_insensitive: bool;
    class_str       : std::string;

    operator=: (out this, negate_: bool, case_insensitive_: bool, class_str_: std::string, str: std::string) = 
    {
        regex_token = str;
        negate = negate_;
        case_insensitive = case_insensitive_;
        class_str = class_str_;
    }

    //  TODO: Rework class generation: Generate check functions for classes.
    parse: (inout ctx: parse_context) -> token_ptr = 
    {
        if ctx..current() != '[' { return nullptr; }

        start_pos := ctx..get_pos();

        supported_classes: std::vector<std::string> = ("alnum", "alpha", "ascii", "blank", "cntrl", "digits", "graph",
                                                       "lower", "print", "punct", "space", "upper", "word", "xdigit");

        classes: std::vector<std::string> = ();

        //  First step: parse until the end bracket and push single chars, ranges or groups on the class stack.
        is_negate := false;
        first     := true;
        range     := false;
        while ctx..next_in_class() && (ctx..current() != ']' || first) 
        {
            if ctx..current() == '^' 
            {
                is_negate = true;
                continue; // Skip rest of the loop. Also the first update.
            }

            if ctx..current() == '[' && ctx..peek_in_class() == ':' 
            {
                //  We have a character class.
                _ = ctx..next_n(2);  // Skip [:

                name: std::string = "";
                if !ctx..grab_until(":]", out name) { return ctx..error("Could not find end of character class."); }
                if supported_classes..end() == std::find(supported_classes..begin(), supported_classes..end(), name) {
                    return ctx..error("Unsupported character class. Supported ones are: (string_util::join(supported_classes))$");
                }

                classes..push_back("[:(name)$:]");

                _ = ctx..next(); // Skip ':' pointing to the ending ']'.
            }
            else if ctx..current() == '\\' 
            {
                if ctx..next_no_skip()  && (ctx..current() != ']') 
                {
                    if  ' ' == ctx..current() 
                        && ctx..get_modifiers()..has(expression_flags::perl_code_syntax) 
                        && ctx..get_modifiers()..has(expression_flags::perl_code_syntax_in_classes) 
                    {
                        classes..push_back(std::string(1, ctx..current()));
                    }
                    else {
                        name := "";
                        if      'd' == ctx..current() { name = "short_digits"; }
                        else if 'D' == ctx..current() { name = "short_not_digits"; }
                        else if 'h' == ctx..current() { name = "short_hor_space"; }
                        else if 'H' == ctx..current() { name = "short_not_hor_space"; }
                        else if 's' == ctx..current() { name = "short_space"; }
                        else if 'S' == ctx..current() { name = "short_not_space"; }
                        else if 'v' == ctx..current() { name = "short_ver_space"; }
                        else if 'V' == ctx..current() { name = "short_not_ver_space"; }
                        else if 'w' == ctx..current() { name = "short_word"; }
                        else if 'W' == ctx..current() { name = "short_not_word"; }
                        else {
                            return ctx..error("Unknown group escape.");
                        }
                        classes..push_back("[:(name)$:]");
                    }
                } else {
                    return ctx..error("Escape without a following character.");
                }
            }
            else if ctx..current() == '-' 
            {
                if first { // Literal if first entry.
                    classes..push_back("(ctx..current())$");
                } else {
                    range = true;
                }
            }
            else 
            {
                if range { // Modify last element to be a range.
                    classes..back() += "-(ctx..current())$";
                    range = false;
                }
                else {
                    classes..push_back("(ctx..current())$");
                }
            }

            first = false;
        }

        if ctx..current() != ']' {
            return ctx..error("Error end of character class definition before terminating ']'.");
        }
        end_pos := ctx..get_pos();

        if range { // If '-' is last entry treat it as a literal char.
            classes..push_back("-");
        }

        // Second step: Wrap the item on the class stack with corresponding class implementation.
        for classes do (inout cur) 
        {
            if cur..starts_with("[:") {
                name := cur..substr(2, cur..size() - 4);
                cur = create_matcher("(name)$_class", "");
            }
            else if 1 != cur..size() {
                cur = create_matcher("range_class_entry", "'(cur[0])$', '(cur[2])$'");
            }
            else {
                cur = create_matcher("single_class_entry", "'(cur)$'");
            }
        }

        inner      := string_util::join(classes);
        string_rep := ctx..get_range(start_pos, end_pos);
        return shared.new<class_token>(
            is_negate, 
            ctx..get_modifiers()..has(expression_flags::case_insensitive), 
            inner, 
            string_rep
            );
    }

    generate_code: (override this, inout ctx: generation_context) = 
    {
        ctx..add_check("class_token_matcher<char, (negate)$, (case_insensitive)$, (class_str)$>::match((ctx..match_parameters())$)");
    }

    private create_matcher: (name: std::string, template_arguments: std::string) -> std::string = 
    {
        sep := ", ";
        if template_arguments..empty() { sep = ""; }

        return "::cpp2::regex::(name)$<char(sep)$(template_arguments)$>";
    }
}


class_token_matcher: <CharT, negate: bool, case_insensitive: bool, List ...> type =
{
    match: (inout cur, inout ctx) -> bool = 
    {
        if constexpr case_insensitive 
        {
            if  cur != ctx.end 
                && negate != ( 
                       match_any<List...>(string_util::safe_tolower(cur*)) 
                    || match_any<List...>(string_util::safe_toupper(cur*))
                    ) 
            {
                cur += 1;
                return true;
            }
            else {
                return false;
            }
        }
        else 
        {
            if cur != ctx.end && negate != match_any<List...>(cur*) {
                cur += 1;
                return true;
            }
            else {
                return false;
            }
        }
    }

    private match_any: <First, Other ...> (c: CharT) -> bool = 
    {
        r: bool = First::includes(c);

        if !r {
            if constexpr 0 != sizeof...(Other) {
                r = match_any<Other...>(c);
            }
        }

        return r;
    }

    // TODO: Implement proper to string
    // to_string: () -> bstring<CharT> = {
    //     r: bstring<CharT> = "[";
    //     if negate {
    //         r += "^";
    //     }
    //     r += (bstring<CharT>() + ... + List::to_string());
    //     r += "]";

    //     return r;
    // }
}


//  Regex syntax: \a or \n or \[
//
escape_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if ctx..current() != '\\' { return nullptr; }


    if std::string::npos == std::string("afenrt^.[]()*{}?+|\\")..find(ctx..peek()) {
        return nullptr;
    }

    _ = ctx..next(); // Skip escape

    if std::string::npos != std::string("afenrt\\")..find(ctx..current()) 
    {
        // Escape of string special char
        t : char = '\0';
        if      'a' == ctx..current() { t = '\a'; }
        else if 'f' == ctx..current() { t = '\f'; }
        else if 'e' == ctx..current() { t = '\x1b'; }
        else if 'n' == ctx..current() { t = '\n'; }
        else if 'r' == ctx..current() { t = '\r'; }
        else if 't' == ctx..current() { t = '\t'; }
        else if '\\' == ctx..current() { t = '\\'; }
        else { return ctx..error("Internal: missing switch case for special escape."); }

        r: = shared.new<char_token>(t, false);
        r*..set_string("\\(ctx..current())$");
        return r;
    } 
    else 
    {
        // Escape of regex special char
        r := shared.new<char_token>(ctx..current(), false);
        r*..set_string("\\(ctx..current())$");
        return r;
    }

}


//  Regex syntax: \K Example: ab\Kcd
//
global_group_reset_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if !(ctx..current() == '\\' && ctx..peek() == 'K') { return nullptr; }

    _ = ctx..next(); // Skip escape.
    return shared.new<regex_token_code>("\\K", "ctx..set_group_start(0, r.pos);");
}


//  Regex syntax: \<number>  Example: \1
//                \g{name_or_number}
//                \k{name_or_number}
//                \k<name_or_number>
//                \k'name_or_number'
//
group_ref_token: @polymorphic_base type = 
{
    this            : regex_token = ();

    id              : int;
    case_insensitive: bool;

    operator=:(out this, id_: int, case_insensitive_: bool, str: std::string) = 
    {
        regex_token      = str;
        id               = id_;
        case_insensitive = case_insensitive_;
    }

    parse: (inout ctx: parse_context) -> token_ptr = 
    {
        if ctx..current() != '\\' { return nullptr; }

        str : std::string = "\\";
        group : std::string = "";

        if '0' <= ctx..peek() <= '9' 
        {
            _ = ctx..next(); // Skip escape
            group = ctx..grab_number();

            if group..size() >= 3 as size_t 
            {
                // Octal syntax (\000) not a group ref matcher.
                number := 0;
                if !string_util::string_to_int(group, number, 8) { return ctx..error("Could not convert octal to int."); }

                number_as_char : char = unsafe_narrow<char>(number);

                token := shared.new<char_token>(number_as_char, ctx..get_modifiers()..has(expression_flags::case_insensitive));
                token*..set_string("\\(string_util::int_to_string<8>(number_as_char as int))$");

                return token;
            }

            str += group;
            // Regular group ref
        }
        else if 'g' == ctx..peek() 
        {
            _ = ctx..next(); // Skip escape
            if !ctx..next() { return ctx..error("Group escape without a following char."); } // Skip g

            str += "g";

            if ctx..current() == '{' {
                str += "{";
                if !(ctx..next() && ctx..grab_until('}', out group)) { return ctx..error("No ending bracket."); }

                str += group + "}";
            }
            else {
                group = ctx..grab_number();
                str += group;
            }
        }
        else if 'k' == ctx..peek() 
        {
            _ = ctx..next(); // Skip escape
            if !ctx..next() { return ctx..error("Group escape without a following char."); } // Skip k

            str += "k";

            term_char := '\0';
            if ctx..current() == '{' { term_char = '}'; }
            else if ctx..current() == '<' { term_char = '>'; }
            else if ctx..current() == '\'' { term_char = '\''; }
            else {
                return ctx..error("Group escape has wrong operator.");
            }

            str += ctx..current();

            if !(ctx..next() && ctx..grab_until(term_char, out group)) { return ctx..error("No ending bracket."); }

            str += group + term_char;
        }
        else 
        {
            // No group ref matcher
            return nullptr;
        }

        // Parse the group
        group = string_util::trim_copy(group);
        group_id : int = 0;
        if string_util::string_to_int(group, group_id) 
        {
            if group_id < 0 {
                group_id = ctx..get_cur_group() + group_id;

                if group_id < 1 { // Negative and zero are no valid groups.
                    return ctx..error("Relative group reference does not reference a valid group. (Would be (group_id)$.)");
                }
            }

            if group_id >= ctx..get_cur_group() {
                return ctx..error("Group reference is used before the group is declared.");
            }
        }
        else 
        {
            // Named group
            group_id = ctx..get_named_group(group);
            if -1 == group_id { return ctx..error("Group names does not exist. (Name is: (group)$)");}
        }

        return shared.new<group_ref_token>(group_id, ctx..get_modifiers()..has(expression_flags::case_insensitive), str);
    }

    generate_code: (override this, inout ctx: generation_context) = {
        ctx..add_check("group_ref_token_matcher<char, (id)$, (case_insensitive)$>((ctx..match_parameters())$)");
    }
}


group_ref_token_matcher: <CharT, group: int, case_insensitive: bool> (inout cur, inout ctx) -> bool = 
{
    g := ctx..get_group(group);

    group_pos := g.start;
    while 
        group_pos != g.end 
        && cur != ctx.end 
    next (group_pos++, cur++) 
    {
        if constexpr case_insensitive {
            if string_util::safe_tolower(group_pos*) != string_util::safe_tolower(cur*) {
                return false;
            }
        }
        else {
            if group_pos* != cur* {
                return false;
            }
        }
    }

    if group_pos == g.end {
        return true;
    }
    else {
        return false;
    }
}


//  Regex syntax: (<tokens>)      Example: (abc)
//                (?<modifiers)            (?i)
//                (?<modifiers>:<tokens>)  (?i:abc)
//                (?<<name>>:<tokens>)     (?<start>:abc)
//                (?#<comment>)            (#Step 1 finished)
//                (?|<tokens>)             (?|(abc)|(cde))
//                (?=<tokens>)             (?=abc)
//                (?!<tokens>)             (?!abc)
//                (*<name>:<tokens)        (*pla:abc)
//
group_token: @polymorphic_base type = 
{
    this: regex_token = ();

    number: int      = -1;
    inner: token_ptr = nullptr;

    parse_lookahead: (inout ctx: parse_context, syntax: std::string, positive: bool) -> token_ptr = 
    {
        _ = ctx..next(); // Skip last token defining the syntax

        r := shared.new<lookahead_token>(positive);

        old_state := ctx..start_group();
        if !ctx..parse_until(')') { return ctx..error("Lookahead without a closing bracket."); }
        r*.inner = ctx..end_group(old_state);
        r*..set_string("((syntax)$(r*.inner*..to_string())$)");

        return r;
    }

    parse: (inout ctx: parse_context) -> token_ptr = 
    {
        if ctx..current() != '(' { return nullptr; }

        has_id              :=  !ctx..get_modifiers()..has(expression_flags::no_group_captures);
        has_pattern         := true;
        group_name          : std::string = "";
        group_name_brackets := true;
        modifiers           : std::string = "";
        modifiers_change_to : =  ctx..get_modifiers();

        //  Skip the '('
        if !ctx..next() { return ctx..error("Group without closing bracket."); }

        if ctx..current() == '?' 
        {
            //  Special group
            if !ctx..next_no_skip() { return ctx..error("Missing character after group opening.");  }

            if ctx..current() == '<' || ctx..current() == '\'' 
            {
                //  Named group
                end_char := ctx..current();
                if end_char == '<' {
                    end_char = '>';
                } else {
                    group_name_brackets = false;
                }
                has_id = true; // Force id for named groups.
                if !ctx..next() /* skip '<' */ { return ctx..error("Missing ending bracket for named group.");  }
                if !ctx..grab_until(end_char, out group_name) { return ctx..error("Missing ending bracket for named group.");  }
                if !ctx..next() { return ctx..error("Group without closing bracket."); }
            }
            else if ctx..current() == '#' 
            {
                //  Comment
                comment_str : std::string = "";
                _ = ctx..next(); // Skip #
                if !ctx..grab_until(")", out comment_str) { return ctx..error("Group without closing bracket."); }
                //  Do not add comment. Has problems with ranges.

                //  Pop token and add a list. This fixes comments between a token and a range
                if ctx..has_token() {
                    list : token_vec = ();
                    list..push_back(ctx..pop_token());
                    list..push_back(shared.new<regex_token_empty>("(?#(comment_str)$)"));

                    return shared.new<regex_token_list>(list);
                }
                else {
                    return shared.new<regex_token_empty>("(?#(comment_str)$)");
                }
            }
            else if ctx..current() == '|' 
            {
                //  Branch reset group

                if !ctx..next() /* skip '|' */ { return ctx..error("Missing ending bracket for named group.");  }

                old_parser_state := ctx..start_group();
                old_branch_state  := ctx..branch_reset_new_state();
                if !ctx..parse_until(')') { return nullptr; }
                ctx..branch_reset_restore_state(old_branch_state);
                inner_ := ctx..end_group(old_parser_state);

                list: token_vec = (shared.new<regex_token_empty>("(?|"), inner_, shared.new<regex_token_empty>(")"));
                return shared.new<regex_token_list>(list);
            }
            else if ctx..current() == '=' || ctx..current() == '!' 
            {
                return parse_lookahead(ctx, "?(ctx..current())$", ctx..current() == '=');
            }
            else 
            {
                //  Simple modifier
                has_id = false;
                if !ctx..grab_until_one_of("):", out modifiers) { return ctx..error("Missing ending bracket for group."); }
                if !ctx..parser_group_modifiers(modifiers, modifiers_change_to) {
                     return nullptr;
                }

                if ')' == ctx..current() {
                    has_pattern = false;
                }
                else {
                    if !ctx..next() /* skip ':' */ { return ctx..error("Missing ending bracket for group.");  }
                }
            }
        }
        else if ctx..current() == '*' 
        {
            //  Named pattern
            _ = ctx..next(); // Skip *.
            name: std::string = "";
            if !ctx..grab_until(':', out name) { return ctx..error("Missing colon for named pattern.");  }

            if name == "pla" || name == "positive_lookahead" {
                return parse_lookahead(ctx, "*(name)$:", true);
            }
            else if name == "nla" || name == "negative_lookahead" {
                return parse_lookahead(ctx, "*(name)$:", false);
            }
            else {
                return ctx..error("Unknown named group pattern: '(name)$'");
            }
        }

        if has_pattern 
        {
            //  Regular group

            r := shared.new<group_token>();
            if has_id {
                r*.number = ctx..next_group();

                if 0 != group_name..size() {
                    ctx..set_named_group(group_name, r*.number);
                }
            }

            old_state := ctx..start_group();
            ctx..set_modifiers(modifiers_change_to);
            if !ctx..parse_until(')') { return nullptr; }
            r*.inner = ctx..end_group(old_state);
            r*..set_string(gen_string(group_name, group_name_brackets, !has_id, modifiers, r*.inner));

            return r;
        }
        else 
        {
            //  Only a modifier
            ctx..set_modifiers(modifiers_change_to);

            return shared.new<regex_token_empty>("(?(modifiers)$)");
        }
    }

    gen_string: (name: std::string, name_brackets: bool, has_modifier: bool, modifiers: std::string, inner_: token_ptr) -> std::string = 
    {
        start : std::string = "(";
        if 0 != name..size() {
            if name_brackets {
                start += "?<(name..data())$>";
            }
            else {
                start += "?'(name..data())$'";
            }
        }
        else if has_modifier {
            start += "?" + modifiers + ":";
        }

        return start + inner_*..to_string() + ")";
    }

    generate_code: (override this, inout ctx: generation_context) = 
    {
        if -1 != number {
            ctx..add("ctx..set_group_start((number)$, r.pos);");
        }

        inner*..generate_code(ctx);
        if -1 != number {
            ctx..add("ctx..set_group_end((number)$, r.pos);");
            tmp_name := ctx..gen_temp();
            ctx..add("(tmp_name)$_func :=  :() = {");
            ctx..add("  if !r&$*.matched {");
            ctx..add("    ctx&$*..set_group_invalid((number)$);");
            ctx..add("  }");
            ctx..add("};");
            ctx..add("(tmp_name)$ :=  cpp2::regex::make_on_return((tmp_name)$_func);");
            ctx..add("_ = (tmp_name)$;"); // Logic is done in the destructor. Same behavior as for guard objects.
        }
    }

    add_groups: (override this, inout groups: std::set<int>) = 
    {
        inner*..add_groups(groups);
        if -1 != number {
            _ = groups..insert(number);
        }
    }
}


//  Regex syntax: \x<number> or \x{<number>}  Example: \x{62}
//
hexadecimal_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if !(ctx..current() == '\\' && ctx..peek() == 'x') { return nullptr; }

    _ = ctx..next(); // Skip escape.

    if !ctx..next() { return ctx..error("x escape without number.");}

    has_brackets := false;
    number_str: std::string = "";
    if '{' == ctx..current() {
        //  Bracketed
        has_brackets = true;
        _  = ctx..next(); // Skip '{'
        if !ctx..grab_until('}', out number_str) { return ctx..error("No ending bracket for \\x"); }
    }
    else {
        //  Grab two chars
        if !ctx..grab_n(2, out number_str) { return ctx..error("Missing hexadecimal digits after \\x."); }
    }

    number := 0;
    if !string_util::string_to_int(number_str, number, 16) { return ctx..error("Could not convert hexadecimal to int."); }

    // TODO: Change for unicode.
    number_as_char : char = unsafe_narrow<char>(number);

    syntax: std::string = string_util::int_to_string<16>(number_as_char as int);
    if has_brackets {
        syntax = "{(syntax)$}";
    }
    syntax = "\\x(syntax)$";

    r := shared.new<char_token>(number_as_char, ctx..get_modifiers()..has(expression_flags::case_insensitive));
    r*..set_string(syntax);
    return r;
}


//  Regex syntax: $  Example: aa$
//
line_end_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if ctx..current() == '$' || (ctx..current() == '\\' && ctx..peek() == '$') {
        if (ctx..current() == '\\') { _ = ctx..next(); } // Skip escape
        return shared.new<regex_token_check>("$", "line_end_token_matcher<char, (ctx..get_modifiers()..has(expression_flags::multiple_lines))$, true>");
    }
    else if ctx..current() == '\\' && (ctx..peek() == 'z' || ctx..peek() == 'Z') {
        _ = ctx..next(); // Skip escape

        negate := ctx..current() == 'Z';
        return shared.new<regex_token_check>("\\(ctx..current())$", "line_end_token_matcher<char, false, (negate)$>");
    }
    else {
        return nullptr;
    }
}

line_end_token_matcher: <CharT, match_new_line: bool, match_new_line_before_end: bool> (cur, inout ctx) -> bool = 
{
    if cur == ctx.end || (match_new_line && cur* == '\n') {
        return true;
    }
    else if match_new_line_before_end && (cur* == '\n' && (cur + 1) == ctx.end) { // Special case for new line at end.
        return true;
    }
    else {
        return false;
    }
}


//  Regex syntax: ^  Example: ^aa
//
line_start_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if ctx..current() != '^' && !(ctx..current() == '\\' && ctx..peek() == 'A') { return nullptr; }

    if ctx..current() == '\\' {
        _ = ctx..next();
        return shared.new<regex_token_check>("\\A", "line_start_token_matcher<char, false>");
    }
    else {
        return shared.new<regex_token_check>("^", "line_start_token_matcher<char, (ctx..get_modifiers()..has(expression_flags::multiple_lines))$>");
    }
}

line_start_token_matcher: <CharT, match_new_line: bool> (cur, inout ctx) -> bool = 
{
    return cur == ctx.begin || // Start of string
           (match_new_line && (cur - 1)* == '\n'); // Start of new line
}


//  Regex syntax: (?=) or (?!) or (*pla), etc.  Example: (?=AA)
//
//  Parsed in group_token.
//
lookahead_token: @polymorphic_base type = 
{
    this: regex_token = ("");

    protected positive: bool;
    public    inner   : token_ptr = nullptr;

    operator=: (out this, positive_: bool) = {
        positive = positive_;
    }

    generate_code: (override this, inout ctx: generation_context) = {
        inner_name := ctx..generate_func(inner);

        ctx..add_check("lookahead_token_matcher<char, (positive)$>((ctx..match_parameters())$, (inner_name)$)");
    }

    add_groups: (override this, inout groups: std::set<int>) = {
        inner*..add_groups(groups);
    }
}

lookahead_token_matcher: <CharT, positive: bool> (cur, inout ctx, func) -> bool = 
{
    r := func(cur, ctx, true_end_func());
    if !positive {
        r.matched = !r.matched;
    }

    return r.matched;
}


// Named character classes
//
named_class_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if ctx..current() != '\\' { return nullptr; }

    name := "";
    c_next := ctx..peek();

    if      'd' == c_next { name = "named_class_digits"; }
    else if 'D' == c_next { name = "named_class_not_digits"; }
    else if 'h' == c_next { name = "named_class_hor_space"; }
    else if 'H' == c_next { name = "named_class_not_hor_space"; }
    else if 'N' == c_next { name = "named_class_no_new_line"; }
    else if 's' == c_next { name = "named_class_space"; }
    else if 'S' == c_next { name = "named_class_not_space"; }
    else if 'v' == c_next { name = "named_class_ver_space"; }
    else if 'V' == c_next { name = "named_class_not_ver_space"; }
    else if 'w' == c_next { name = "named_class_word"; }
    else if 'W' == c_next { name = "named_class_not_word"; }
    else                  { return nullptr; }

    _ = ctx..next(); // Skip escape

    return shared.new<regex_token_check>("\\(ctx..current())$", "(name)$<char, (ctx..get_modifiers()..has(expression_flags::case_insensitive))$>::match");
}


named_class_no_new_line   : <CharT, case_insensitive: bool> type == class_token_matcher<CharT,  true, case_insensitive, single_class_entry<CharT, '\n'>>;
named_class_digits        : <CharT, case_insensitive: bool> type == class_token_matcher<CharT, false, case_insensitive, digits_class<CharT>>;
named_class_hor_space     : <CharT, case_insensitive: bool> type == class_token_matcher<CharT, false, case_insensitive, hor_space_class<CharT>>;
named_class_space         : <CharT, case_insensitive: bool> type == class_token_matcher<CharT, false, case_insensitive, space_class<CharT>>;
named_class_ver_space     : <CharT, case_insensitive: bool> type == class_token_matcher<CharT, false, case_insensitive, ver_space_class<CharT>>;
named_class_word          : <CharT, case_insensitive: bool> type == class_token_matcher<CharT, false, case_insensitive, word_class<CharT>>;

named_class_not_digits    : <CharT, case_insensitive: bool> type == class_token_matcher<CharT,  true, case_insensitive, digits_class<CharT>>;
named_class_not_hor_space : <CharT, case_insensitive: bool> type == class_token_matcher<CharT,  true, case_insensitive, hor_space_class<CharT>>;
named_class_not_space     : <CharT, case_insensitive: bool> type == class_token_matcher<CharT,  true, case_insensitive, space_class<CharT>>;
named_class_not_ver_space : <CharT, case_insensitive: bool> type == class_token_matcher<CharT,  true, case_insensitive, ver_space_class<CharT>>;
named_class_not_word      : <CharT, case_insensitive: bool> type == class_token_matcher<CharT,  true, case_insensitive, word_class<CharT>>;


//  Regex syntax: \o{<number>}  Example: \o{142}
//
octal_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if !(ctx..current() == '\\' && ctx..peek() == 'o') { return nullptr; }

    _ = ctx..next(); // Skip escape.

    if !ctx..next()          { return ctx..error("o escape without number.");}
    if ctx..current() != '{' { return ctx..error("Missing opening bracket for \\o."); }

    number_str: std::string = "";
    _  = ctx..next(); // Skip '{'
    if !ctx..grab_until('}', out number_str) { return ctx..error("No ending bracket for \\o"); }

    number := 0;
    if !string_util::string_to_int(number_str, number, 8) { return ctx..error("Could not convert octal to int."); }

    // TODO: Change for unicode.
    number_as_char : char = unsafe_narrow<char>(number);

    syntax: std::string = "\\o{(string_util::int_to_string<8>(number_as_char as int))$}";
    r := shared.new<char_token>(number_as_char, ctx..get_modifiers()..has(expression_flags::case_insensitive));
    r*..set_string(syntax);
    return r;
}

// TODO: @enum as template parameter currently not working. See issue https://github.com/hsutter/cppfront/issues/1147


//  Options for range matching.
range_flags: type = {
    not_greedy: int == 1;  // Try to take as few as possible.
    greedy:     int == 2;  // Try to take as many as possible.
    possessive: int == 3;  // Do not give back after a greedy match. No backtracking.
}


//  Regex syntax: <matcher>{min, max}  Example: a{2,4}
//
range_token: @polymorphic_base type = 
{
    this                 : regex_token = ("");

    protected min_count  : int         = -1;
    protected max_count  : int         = -1;
    protected kind       : int         = range_flags::greedy;
    protected inner_token: token_ptr   = nullptr;

    operator=: (out this) = {}

    parse: (inout ctx: parse_context) -> token_ptr = 
    {
        r := shared.new<range_token>();
        if ctx..current() == '{' 
        {
            if !ctx..has_token() { return ctx..error("'{' without previous element."); }

            inner: std::string = "";
            if !ctx..grab_until('}', out inner) { return ctx..error("Missing closing bracket '}'."); }

            inner = string_util::trim_copy(inner..substr(1)); // Remove '{' and white spaces.
            if inner..empty() { return ctx..error("Empty range specifier. Either '{n}', '{n,}', '{,m}' '{n,m}'"); }

            // Non-greedy or possessive
            r*..parse_modifier(ctx);

            // Get range arguments
            min_count_str: std::string = "-1";
            max_count_str: std::string = "-1";

            sep: size_t = inner..find(",");
            if sep == std::string::npos 
            {
                min_count_str = inner;
                max_count_str = inner;
                if !string_util::string_to_int(inner, r*.min_count) { return ctx..error("Could not convert range to number."); }
                r*.max_count = r*.min_count;
            }
            else 
            {
                inner_first: std::string = string_util::trim_copy(inner..substr(0, sep));
                inner_last: std::string = string_util::trim_copy(inner..substr(sep + 1));

                if (inner_first..empty() && inner_last..empty()) {
                    return ctx..error("Empty range specifier. Either '{n}', '{n,}', '{,m}' '{n,m}'");
                }

                if !inner_first..empty() {
                    min_count_str = inner_first;
                    if !string_util::string_to_int(inner_first, r*.min_count) { return ctx..error("Could not convert range to number."); }
                }
                if !inner_last..empty() {
                    max_count_str = inner_last;
                    if !string_util::string_to_int(inner_last, r*.max_count) { return ctx..error("Could not convert range to number."); }
                }
            }

            // Check validity of the range.
            if -1 != r*.min_count {
                if !(0 <= r*.min_count) {
                    return ctx..error("Min value in range is negative. Have (r*.min_count)$)");
                }
            }
            if -1 != r*.max_count {
                if !(0 <= r*.max_count) {
                    return ctx..error("Max value in range is negative. Have (r*.max_count)$)");
                }
                if -1 != r*.min_count {
                    if !(r*.min_count <= r*.max_count) {
                        return ctx..error("Min and max values in range are wrong it should hold 0 <= min <= max. Have 0 <= (r*.min_count)$ <= (r*.max_count)$");
                    }
                }
            }

            r*.inner_token = ctx..pop_token();
            r*.string_rep = r*.inner_token*..to_string() + r*..gen_range_string() + r*..gen_mod_string();

            return r;
        }

        return nullptr;
    }

    parse_modifier: (inout this, inout ctx: parse_context) = 
    {
        if ctx..peek() == '?' {
            kind = range_flags::not_greedy;
            _ = ctx..next();
        }
        else if ctx..peek() == '+' {
            kind = range_flags::possessive;
            _ = ctx..next();
        }
    }

    gen_mod_string: (this) -> std::string = 
    {
        if kind == range_flags::not_greedy {
            return "?";
        }
        else if kind == range_flags::possessive {
            return "+";
        }
        else {
            return "";
        }
    }

    gen_range_string: (this) -> std::string = 
    {
        r : std::string = "";
        if min_count == max_count {
            r += "{(min_count)$}";
        }
        else if min_count == -1 {
            r += "{,(max_count)$}";
        }
        else if max_count == -1 {
            r += "{(min_count)$,}";
        }
        else {
            r += "{(min_count)$,(max_count)$}";
        }

        return r;
    }

    generate_code: (override this, inout ctx: generation_context) = 
    {
        inner_name := ctx..generate_func(inner_token);
        groups: std::set<int> = ();
        inner_token*..add_groups(groups);
        reset_name := ctx..generate_reset(groups);

        next_name := ctx..next_func_name();
        ctx..add_statefull(next_name, "cpp2::regex::range_token_matcher<char, (min_count)$, (max_count)$, (kind)$>::match((ctx..match_parameters())$, (inner_name)$, (reset_name)$, other, (next_name)$)");
    }

    add_groups: (override this, inout groups: std::set<int>) = {
        inner_token*..add_groups(groups);
    }

}


range_token_matcher: <CharT, min_count: int, max_count: int, kind: int> type = 
{

    match: <Iter> (cur: Iter, inout ctx, inner, reset_func, end_func, tail) -> _ = 
    {
        if range_flags::possessive == kind {
            return match_possessive(cur, ctx, inner, end_func, tail);
        }
        else if range_flags::greedy == kind {
            return match_greedy(0, cur, ctx.end, ctx, inner, reset_func, end_func, tail);
        }
        else { // range_flags::not_greedy == kind
            return match_not_greedy(cur, ctx, inner, end_func, tail);
        }
    }

    private is_below_upper_bound: (count: int) -> bool = {
        if -1 == max_count { return true; }
        else { return count < max_count; }
    }

    private is_below_lower_bound: (count: int) -> bool = {
        if -1 == min_count { return false; }
        else { return count < min_count; }
    }

    private is_in_range: (count: int) -> bool = {
        if -1 != min_count && count < min_count { return false; }
        if -1 != max_count && count > max_count { return false; }
        return true;
    }

    private match_min_count: <Iter> (cur: Iter, inout ctx, inner, end_func, inout count_r: int) -> _ = 
    {   // TODO: count_r as out parameter introduces a performance loss.
        res := ctx..pass(cur);
        count := 0;

        while is_below_lower_bound(count) && res.matched {
            res = inner(res.pos, ctx, end_func);
            if res.matched {
                count += 1;
            }
        }

        count_r = count;
        return res;
    }

    private match_greedy: <Iter> (count: int, cur: Iter, last_valid: Iter, inout ctx, inner, reset_func, end_func, other) -> match_return<Iter> = 
    {
        inner_call := :(tail_cur, inout tail_ctx) -> _ == {
            return match_greedy((count + 1)$, tail_cur, (cur)$, tail_ctx, (inner)$, (reset_func)$, (end_func)$, (other)$);
        };
        is_m_valid := true;
        r := ctx..fail();
        if is_below_upper_bound(count) && (is_below_lower_bound(count) || cur != last_valid) {
            is_m_valid = false;  // Group ranges in M are invalidated through the call.
            r = inner(cur, ctx, inner_call);
        }

        if !r.matched && is_in_range(count) 
        {
            //  The recursion did not yield a match try now the tail
            r = other(cur, ctx, end_func);

            if r.matched && !is_m_valid{
                //  We have a match rematch M if required
                reset_func(ctx);

                if count > 0 {
                    _ = inner(last_valid, ctx, true_end_func());
                }
            }
        }

        return r;
    }

    private match_possessive: <Iter>(cur: Iter, inout ctx, inner, end_func, other) -> match_return<Iter> = 
    {
        count :=0;
        r := match_min_count(cur, ctx, inner, end_func, count);

        if !r.matched {
          return r;
        }

        pos := r.pos;
        while 
            r.matched 
            && is_below_upper_bound(count) 
        {
            r = inner(pos, ctx, true_end_func());

            if pos == r.pos {
                break; // Break infinite loop.
            }
            if r.matched {
                count += 1;
                pos = r.pos;
            }
        }

        return other(pos, ctx, end_func);
    }

    private match_not_greedy: <Iter> (cur: Iter, inout ctx, inner, end_func, other) -> match_return<Iter> = 
    {
        count := 0;
        start := match_min_count(cur, ctx, inner, end_func, count);
        if !start.matched {
          return start;
        }

        pos := start.pos;
        while is_below_upper_bound(count) 
        {
            o:= other(pos, ctx, end_func);
            if o.matched {
                return o;
            }

            r:= inner(pos, ctx, end_func);
            if !r.matched {
                return ctx..fail();
            }
            count += 1;
            pos = r.pos;
        }

        return other(pos, ctx, end_func); // Upper bound reached.
    }
}


//  Regex syntax: *, +, or ?  Example: aa*
//
special_range_token: @polymorphic_base type = 
{
    this : range_token = ();

    parse: (inout ctx: parse_context) -> token_ptr = 
    {
        r := shared.new<special_range_token>();
        symbol: char = '\0';
        if ctx..current() == '*' {
            r*.min_count = 0;
            r*.max_count = -1;
            symbol = '*';
        }
        else if ctx..current() == '+' {
            r*.min_count = 1;
            r*.max_count = -1;
            symbol = '+';
        } else if ctx..current() == '?' {
            r*.min_count = 0;
            r*.max_count = 1;
            symbol = '?';
        } else {
            return nullptr;
        }

        if !ctx..has_token() { return ctx..error("'(ctx..current())$' without previous element."); }


        r*..parse_modifier(ctx);

        r*.inner_token = ctx..pop_token();
        r*.string_rep = r*.inner_token*..to_string() + symbol + r*..gen_mod_string();
        return r;
    }
}


//  Regex syntax: \b or \B  Example: \bword\b
//
//  Matches the start end end of word boundaries.
//
word_boundary_token_parse: (inout ctx: parse_context) -> token_ptr = 
{
    if ctx..current() != '\\' { return nullptr; }

    if ctx..peek() == 'b' {
        _ = ctx..next();
        return shared.new<regex_token_check>("\\b", "word_boundary_token_matcher<char, false>");
    }
    else if ctx..peek() == 'B' {
        _ = ctx..next();
        return shared.new<regex_token_check>("\\B", "word_boundary_token_matcher<char, true>");
    }
    else {
        return nullptr;
    }
}

word_boundary_token_matcher: <CharT, negate: bool> (inout cur, inout ctx) -> bool = 
{
    words : word_class<CharT> = ();
    is_match := false;
    if cur == ctx.begin { // String start
        if cur != ctx.end { // No empty string
            is_match = words..includes(cur*);
        }
    }
    else if cur == ctx.end { // String end
        is_match = words..includes((cur - 1)*);
    }
    else { // Middle of string
        is_match =
                (words..includes((cur - 1)*) && !words..includes(cur*))  // End of word: \w\W
            || (!words..includes((cur - 1)*) && words..includes(cur*)); // Start of word: \W\w
    }
    if negate {
        is_match = !is_match;
    }

    return is_match;
}


//-----------------------------------------------------------------------
//
//  Regular expression implementation.
//
//-----------------------------------------------------------------------
//

//  Regular expression implementation
regular_expression: <CharT, matcher_wrapper> type = 
{
    matcher: <Iter> type == matcher_wrapper_type<matcher_wrapper, Iter, CharT>; // TODO: Remove when nested types are allowed: https://github.com/hsutter/cppfront/issues/727
    context: <Iter> type == matcher_context_type<matcher<Iter>>;                      // TODO: Remove when nested types are allowed: https://github.com/hsutter/cppfront/issues/727

    search_return: <Iter> type = 
    {
        public matched: bool;
        public ctx:     context<Iter>;
        public pos:     int;

        operator=:(out this, matched_: bool, ctx_: context<Iter>, pos_: Iter) = {
            matched = matched_;
            ctx = ctx_;
            pos = unsafe_narrow<int>(std::distance(ctx_.begin, pos_));
        }

        group_number: (this) ctx..size();
        group:        (this, g: int) ctx..get_group_string(g);
        group_start:  (this, g: int) ctx..get_group_start(g);
        group_end:    (this, g: int) ctx..get_group_end(g);

        group:        (this, g: bstring<CharT>) group(get_group_id(g));
        group_start:  (this, g: bstring<CharT>) group_start(get_group_id(g));
        group_end:    (this, g: bstring<CharT>) group_end(get_group_id(g));

        private get_group_id: (this, g: bstring<CharT>) -> _ = {
            group_id := matcher<Iter>::get_named_group_index(g);
            if -1 == group_id {
                // TODO: Throw error.
            }
            return group_id;
        }
    }

    match: (in this, str: bview<CharT>)                 match(str..begin(), str..end());
    match: (in this, str: bview<CharT>, start)          match(get_iter(str, start), str..end());
    match: (in this, str: bview<CharT>, start, length)  match(get_iter(str, start), get_iter(str, start + length));
    match: <Iter> (in this, start: Iter, end: Iter) -> search_return<Iter> = 
    {
        ctx: context<Iter> = (start, end);

        r := matcher<Iter>::entry(start, ctx);
        return search_return<Iter>(r.matched && r.pos == end, ctx, r.pos);
    }

    search: (in this, str: bview<CharT>)                 search(str..begin(), str..end());
    search: (in this, str: bview<CharT>, start)          search(get_iter(str, start), str..end());
    search: (in this, str: bview<CharT>, start, length)  search(get_iter(str, start), get_iter(str, start + length));
    search: <Iter> (in this, start: Iter, end: Iter) -> search_return<Iter> = 
    {
        ctx: context<Iter> = (start, end);
        r := ctx..fail();

        cur:= start;
        while true next (cur++) {
            r = matcher<Iter>::entry(cur, ctx);
            if r.matched {
                break;
            }

            if cur == ctx.end {
                break;
            }
        }

        return search_return<Iter>(r.matched, ctx, r.pos);
    }

    to_string: (in this) matcher_wrapper::to_string();

    //  Helper functions
    //
    private get_iter: (str: bview<CharT>, pos) -> _ = {
        if pos < str..size() {
            return str..begin() + pos;
        }
        else {
            return str..end();
        }
    }
}


//-----------------------------------------------------------------------
//
//  Parser for regular expression.
//
//-----------------------------------------------------------------------
//

//  Parser and generator for regular expressions.
regex_generator: <Error_out> type = 
{
    regex:           std::string_view;
    modifier:        std::string = "";
    modifier_escape: std::string = "";

    error_out:       Error_out;

    source:          std::string = "";

    operator=: (out this, r: std::string_view, e: Error_out) = {
        regex = r;
        error_out = e;
    }

    parse:(inout this) -> std::string = 
    {
        // Extract modifiers and adapt regex.
        extract_modifiers();

        parse_ctx: parse_context = (regex, error_out);
        if !parse_ctx..parse(modifier) {
            return "";
        }

        source += "{\n";
        source += " wrap: <Iter, CharT> type = {\n"; // TODO: Remove wrapper when template template parameters are available.
        source += "  context: type == cpp2::regex::match_context<CharT, Iter, (parse_ctx..get_cur_group())$>;";

        gen_ctx: generation_context = ();
        source += gen_ctx..run(parse_ctx..get_as_token());
        source += "  entry: (cur: Iter, inout ctx: context) -> cpp2::regex::match_return<Iter> = {\n";
        source += "    ctx..set_group_start(0, cur);\n";
        source += "    r := (gen_ctx..get_entry_func())$(cur, ctx, cpp2::regex::true_end_func());\n";
        source += "    if r.matched { ctx..set_group_end(0, r.pos); }\n";
        source += "    return r;\n";
        source += "  }\n";

        source += gen_ctx..create_named_group_lookup(parse_ctx.named_groups);
        source += "}\n";

        string := parse_ctx..get_as_token()*..to_string();
        source += "  to_string: () -> std::string = { return R\"((modifier_escape)$(string)$(modifier_escape)$(modifier)$)\"; }\n";
        source += "}\n";

        _ = parse_ctx;

        return source;
    }

    private extract_modifiers: (inout this) = 
    {
        if regex..find_first_of("'/") == 0 {
            mod_token: char = regex[0];

            end_pos := regex..rfind(mod_token);
            if end_pos != 0 {
                // Found valid start end escape
                modifier = regex..substr(end_pos + 1);
                modifier_escape = mod_token;
                regex = regex..substr(1, end_pos - 1);
            }
        }
    }
}

generate_regex: <Err> (regex: std::string_view, err: Err) -> std::string = 
{
    parser: regex_generator<Err> = (regex, err);
    r := parser..parse();
    _ = parser;
    return r;
}

}
}


#endif