//  Copyright 2022-2024 Herb Sutter
//  SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//  
//  Part of the Cppfront Project, under the Apache License v2.0 with LLVM Exceptions.
//  See https://github.com/hsutter/cppfront/blob/main/LICENSE for license information.


//===========================================================================
//  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;

cpp2: namespace = {

regex: namespace = {

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

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

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

    matched: bool = false;
}

//  Return value for every matcher.
// 
match_return: @struct<noforward> <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::unchecked_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::unchecked_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<noforward> type = 
{
    operator(): (in this, cur, inout ctx) = ctx..pass(cur);
}


//  Empty group reset function.
//
no_reset: @struct<noforward> 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>>>;


//  Regex syntax: |  Example: ab|ba
//
//  Non greedy implementation. First alternative that matches is chosen.
//
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_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;
}


// 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_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;
    // }
}


// Named short classes
//
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: \<number>  Example: \1
//                \g{name_or_number}
//                \k{name_or_number}
//                \k<name_or_number>
//                \k'name_or_number'
//
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: $  Example: aa$
//
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_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_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;
}


// 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_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: \b or \B  Example: \bword\b
//
//  Matches the start end end of word boundaries.
//
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 = unchecked_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();
        }
    }
}

}
}
#endif