<commit_before>#include "regex_impl.hh"

#include "exception.hh"
#include "string.hh"
#include "unicode.hh"
#include "unit_tests.hh"
#include "utf8.hh"
#include "utf8_iterator.hh"
#include "string_utils.hh"
#include "vector.hh"

#include <cstring> 

namespace Kakoune
{

constexpr Codepoint CompiledRegex::StartChars::other;

struct ParsedRegex
{
    enum Op : char
    {
        Literal,
        AnyChar,
        Class,
        CharacterType,
        Sequence,
        Alternation,
        LineStart,
        LineEnd,
        WordBoundary,
        NotWordBoundary,
        SubjectBegin,
        SubjectEnd,
        ResetStart,
        LookAhead,
        NegativeLookAhead,
        LookBehind,
        NegativeLookBehind,
    };

    struct Quantifier
    {
        enum Type : char
        {
            One,
            Optional,
            RepeatZeroOrMore,
            RepeatOneOrMore,
            RepeatMinMax,
        };
        Type type = One;
        bool greedy = true;
        int16_t min = -1, max = -1;

        bool allows_none() const
        {
            return type == Quantifier::Optional or
                   type == Quantifier::RepeatZeroOrMore or
                  (type == Quantifier::RepeatMinMax and min <= 0);
        }

        bool allows_infinite_repeat() const
        {
            return type == Quantifier::RepeatZeroOrMore or
                   type == Quantifier::RepeatOneOrMore or
                  (type == Quantifier::RepeatMinMax and max < 0);
        };
    };

    struct Node;
    using NodeIndex = uint16_t;

    struct Node
    {
        Op op;
        bool ignore_case;
        NodeIndex children_end;
        Codepoint value;
        Quantifier quantifier;
    };

    Vector<Node, MemoryDomain::Regex> nodes;

    Vector<CharacterClass, MemoryDomain::Regex> character_classes;
    size_t capture_count;
};

namespace
{
template<typename Func>
bool for_each_child(const ParsedRegex& parsed_regex, ParsedRegex::NodeIndex index, Func&& func)
{
    const auto end = parsed_regex.nodes[index].children_end;
    for (auto child = index+1; child != end;
         child = parsed_regex.nodes[child].children_end)
    {
        if (func(child) == false)
            return false;
    }
    return true;
}

template<typename Func>
bool for_each_child_reverse(const ParsedRegex& parsed_regex, ParsedRegex::NodeIndex index, Func&& func)
{
    auto find_last_child = [&](ParsedRegex::NodeIndex begin, ParsedRegex::NodeIndex end) {
        while (parsed_regex.nodes[begin].children_end != end)
            begin = parsed_regex.nodes[begin].children_end;
        return begin;
    };
    const auto first_child = index+1;
    auto end = parsed_regex.nodes[index].children_end;
    while (end != first_child)
    {
        auto child = find_last_child(first_child, end);
        if (func(child) == false)
            return false;
        end = child;
    }
    return true;
}
}

// Recursive descent parser based on naming used in the ECMAScript
// standard, although the syntax is not fully compatible.
struct RegexParser
{
    RegexParser(StringView re)
        : m_regex{re}, m_pos{re.begin(), re}
    {
        m_parsed_regex.capture_count = 1;
        m_parsed_regex.nodes.reserve((size_t)re.length());
        NodeIndex root = disjunction(0);
        kak_assert(root == 0);
    }

    ParsedRegex get_parsed_regex() { return std::move(m_parsed_regex); }

    static ParsedRegex parse(StringView re) { return RegexParser{re}.get_parsed_regex(); }

private:
    struct InvalidPolicy
    {
        Codepoint operator()(Codepoint cp) { throw regex_error{"Invalid utf8 in regex"}; }
    };

    using Iterator = utf8::iterator<const char*, Codepoint, int, InvalidPolicy>;
    using NodeIndex = ParsedRegex::NodeIndex;

    NodeIndex disjunction(unsigned capture = -1)
    {
        NodeIndex index = new_node(ParsedRegex::Alternation);
        get_node(index).value = capture;
        while (true)
        {
            alternative();
            if (at_end() or *m_pos != '|')
                break;
            ++m_pos;
        }
        get_node(index).children_end = m_parsed_regex.nodes.size();

        return index;
    }

    NodeIndex alternative(ParsedRegex::Op op = ParsedRegex::Sequence)
    {
        NodeIndex index = new_node(op);
        while (auto t = term())
        {}
        get_node(index).children_end = m_parsed_regex.nodes.size();

        return index;
    }

    Optional<NodeIndex> term()
    {
        while (modifiers()) // read all modifiers
        {}
        if (auto node = assertion())
            return node;
        if (auto node = atom())
        {
            get_node(*node).quantifier = quantifier();
            return node;
        }
        return {};
    }

    bool accept(StringView expected)
    {
        auto it = m_pos.base();
        for (auto expected_it = expected.begin(); expected_it != expected.end(); ++expected_it)
        {
            if (it == m_regex.end() or *it++ != *expected_it)
                return false;
        }
        m_pos = Iterator{it, m_regex};
        return true;
    }

    bool modifiers()
    {
        if (accept("(?i)"))
        {
            m_ignore_case = true;
            return true;
        }
        if (accept("(?I)"))
        {
            m_ignore_case = false;
            return true;
        }
        return false;
    }

    Optional<NodeIndex> assertion()
    {
        if (at_end())
            return {};

        switch (*m_pos)
        {
            case '^': ++m_pos; return new_node(ParsedRegex::LineStart);
            case '$': ++m_pos; return new_node(ParsedRegex::LineEnd);
            case '\\':
                if (m_pos+1 == m_regex.end())
                    return {};
                switch (*(m_pos+1))
                {
                    case 'b': m_pos += 2; return new_node(ParsedRegex::WordBoundary);
                    case 'B': m_pos += 2; return new_node(ParsedRegex::NotWordBoundary);
                    case 'A': m_pos += 2; return new_node(ParsedRegex::SubjectBegin);
                    case 'z': m_pos += 2; return new_node(ParsedRegex::SubjectEnd);
                    case 'K': m_pos += 2; return new_node(ParsedRegex::ResetStart);
                }
                break;
            case '(':
            {
                Optional<ParsedRegex::Op> lookaround_op;
                constexpr struct { StringView prefix; ParsedRegex::Op op; } lookarounds[] = {
                    { "(?=", ParsedRegex::LookAhead },
                    { "(?!", ParsedRegex::NegativeLookAhead },
                    { "(?<=", ParsedRegex::LookBehind },
                    { "(?<!", ParsedRegex::NegativeLookBehind }
                };
                for (auto& lookaround : lookarounds)
                {
                    if (accept(lookaround.prefix))
                    {
                        lookaround_op = lookaround.op;
                        break;
                    }
                }
                if (not lookaround_op)
                        return {};

                NodeIndex lookaround = alternative(*lookaround_op);
                if (at_end() or *m_pos++ != ')')
                    parse_error("unclosed parenthesis");

                validate_lookaround(lookaround);
                return lookaround;
            }
        }
        return {};
    }

    Optional<NodeIndex> atom()
    {
        if (at_end())
            return {};

        const Codepoint cp = *m_pos;
        switch (cp)
        {
            case '.': ++m_pos; return new_node(ParsedRegex::AnyChar);
            case '(':
            {
                ++m_pos;
                const bool capture = not accept("?:");
                NodeIndex content = disjunction(capture ? m_parsed_regex.capture_count++ : -1);
                if (at_end() or *m_pos++ != ')')
                    parse_error("unclosed parenthesis");
                return content;
            }
            case '\\':
                ++m_pos;
                return atom_escape();
            case '[':
                ++m_pos;
                return character_class();
            case '|': case ')':
                return {};
            default:
                if (contains("^$.*+?[]{}", cp))
                    parse_error(format("unexpected '{}'", cp));
                ++m_pos;
                return new_node(ParsedRegex::Literal, cp);
        }
    }

    NodeIndex atom_escape()
    {
        const Codepoint cp = *m_pos++;

        if (cp == 'Q')
        {
            auto escaped_sequence = new_node(ParsedRegex::Sequence);
            constexpr StringView end_mark{"\\E"};

            auto quote_end = std::search(m_pos.base(), m_regex.end(), end_mark.begin(), end_mark.end());
            while (m_pos != quote_end)
                new_node(ParsedRegex::Literal, *m_pos++);
            get_node(escaped_sequence).children_end = m_parsed_regex.nodes.size();

            if (quote_end != m_regex.end())
                m_pos += 2;

            return escaped_sequence;
        }

        // CharacterClassEscape
        auto class_it = find_if(character_class_escapes, [cp](auto& c) { return c.cp == cp; });
        if (class_it != std::end(character_class_escapes))
            return new_node(ParsedRegex::CharacterType, (Codepoint)class_it->ctype);

        // CharacterEscape
        for (auto& control : control_escapes)
        {
            if (control.name == cp)
                return new_node(ParsedRegex::Literal, control.value);
        }

        auto read_hex = [this](size_t count)
        {
            Codepoint res = 0;
            for (int i = 0; i < count; ++i)
            {
                if (at_end())
                    parse_error("unterminated hex sequence");
                Codepoint digit = *m_pos++;
                Codepoint digit_value;
                if ('0' <= digit and digit <= '9')
                    digit_value = digit - '0';
                else if ('a' <= digit and digit <= 'f')
                    digit_value = 0xa + digit - 'a';
                else if ('A' <= digit and digit <= 'F')
                    digit_value = 0xa + digit - 'A';
                else
                    parse_error(format("invalid hex digit '{}'", digit));

                res = res * 16 + digit_value;
            }
            return res;
        };

        if (cp == '0')
            return new_node(ParsedRegex::Literal, '\0');
        else if (cp == 'c')
        {
            if (at_end())
                parse_error("unterminated control escape");
            Codepoint ctrl = *m_pos++;
            if (('a' <= ctrl and ctrl <= 'z') or ('A' <= ctrl and ctrl <= 'Z'))
                return new_node(ParsedRegex::Literal, ctrl % 32);
            parse_error(format("Invalid control escape character '{}'", ctrl));
        }
        else if (cp == 'x')
            return new_node(ParsedRegex::Literal, read_hex(2));
        else if (cp == 'u')
            return new_node(ParsedRegex::Literal, read_hex(4));

        if (contains("^$\\.*+?()[]{}|", cp)) // SyntaxCharacter
            return new_node(ParsedRegex::Literal, cp);
        parse_error(format("unknown atom escape '{}'", cp));
    }

    void normalize_ranges(Vector<CharacterClass::Range, MemoryDomain::Regex>& ranges)
    {
        if (ranges.empty())
            return;

        // Sort ranges so that we can use binary search
        std::sort(ranges.begin(), ranges.end(),
                  [](auto& lhs, auto& rhs) { return lhs.min < rhs.min; });

        // merge overlapping ranges 
        auto pos = ranges.begin();
        for (auto next = pos+1; next != ranges.end(); ++next)
        {
            if (pos->max + 1 >= next->min)
            {
                if (next->max > pos->max)
                    pos->max = next->max;
            }
            else
                *++pos = *next;
        }
        ranges.erase(pos+1, ranges.end());
    }

    NodeIndex character_class()
    {
        CharacterClass character_class;

        character_class.ignore_case = m_ignore_case;
        character_class.negative = m_pos != m_regex.end() and *m_pos == '^';
        if (character_class.negative)
            ++m_pos;

        while (m_pos != m_regex.end() and *m_pos != ']')
        {
            auto cp = *m_pos++;
            if (cp == '-')
            {
                character_class.ranges.push_back({ '-', '-' });
                continue;
            }

            if (at_end())
                break;

            if (cp == '\\')
            {
                auto it = find_if(character_class_escapes,
                                  [cp = *m_pos](auto& t) { return t.cp == cp; });
                if (it != std::end(character_class_escapes))
                {
                    character_class.ctypes |= it->ctype;
                    ++m_pos;
                    continue;
                }
                else // its just an escaped character
                {
                    cp = *m_pos++;
                    for (auto& control : control_escapes)
                    {
                        if (control.name == cp)
                        {
                            cp = control.value;
                            break;
                        }
                    }
                }
            }

            CharacterClass::Range range = { cp, cp };
            if (*m_pos == '-')
            {
                if (++m_pos == m_regex.end())
                    break;
                if (*m_pos != ']')
                {
                    range.max = *m_pos++;
                    if (range.min > range.max)
                        parse_error("invalid range specified");
                }
                else
                {
                    character_class.ranges.push_back(range);
                    range = { '-', '-' };
                }
            }
            character_class.ranges.push_back(range);
        }
        if (at_end())
            parse_error("unclosed character class");
        ++m_pos;

        if (m_ignore_case)
        {
            for (auto& range : character_class.ranges)
            {
                range.min = to_lower(range.min);
                range.max = to_lower(range.max);
            }
        }

        normalize_ranges(character_class.ranges);

        // Optimize the relatively common case of using a character class to
        // escape a character, such as [*]
        if (character_class.ctypes == CharacterType::None and not character_class.negative and
            character_class.ranges.size() == 1 and
            character_class.ranges.front().min == character_class.ranges.front().max)
            return new_node(ParsedRegex::Literal, character_class.ranges.front().min);

        if (character_class.ctypes != CharacterType::None and not character_class.negative and
            character_class.ranges.empty())
            return new_node(ParsedRegex::CharacterType, (Codepoint)character_class.ctypes);

        auto class_id = m_parsed_regex.character_classes.size();
        m_parsed_regex.character_classes.push_back(std::move(character_class));

        return new_node(ParsedRegex::Class, class_id);
    }

    ParsedRegex::Quantifier quantifier()
    {
        if (at_end())
            return {ParsedRegex::Quantifier::One};

        constexpr int max_repeat = 1000;
        auto read_bound = [max_repeat, this](auto& pos, auto begin, auto end) {
            int16_t res = 0;
            for (; pos != end; ++pos)
            {
                const auto cp = *pos;
                if (cp < '0' or cp > '9')
                    return pos == begin ? (int16_t)-1 : res;
                res = res * 10 + cp - '0';
                if (res > max_repeat)
                    parse_error(format("Explicit quantifier is too big, maximum is {}", max_repeat));
            }
            return res;
        };

        auto check_greedy = [&]() {
            if (at_end() or *m_pos != '?')
                return true;
            ++m_pos;
            return false;
        };

        switch (*m_pos)
        {
            case '*': ++m_pos; return {ParsedRegex::Quantifier::RepeatZeroOrMore, check_greedy()};
            case '+': ++m_pos; return {ParsedRegex::Quantifier::RepeatOneOrMore, check_greedy()};
            case '?': ++m_pos; return {ParsedRegex::Quantifier::Optional, check_greedy()};
            case '{':
            {
                auto it = m_pos+1;
                const int16_t min = read_bound(it, it, m_regex.end());
                int16_t max = min;
                if (*it == ',')
                {
                    ++it;
                    max = read_bound(it, it, m_regex.end());
                }
                if (*it++ != '}')
                   parse_error("expected closing bracket");
                m_pos = it;
                return {ParsedRegex::Quantifier::RepeatMinMax, check_greedy(), min, max};
            }
            default: return {ParsedRegex::Quantifier::One};
        }
    }

    NodeIndex new_node(ParsedRegex::Op op, Codepoint value = -1,
                          ParsedRegex::Quantifier quantifier = {ParsedRegex::Quantifier::One})
    {
        constexpr auto max_nodes = std::numeric_limits<uint16_t>::max();
        const NodeIndex res = m_parsed_regex.nodes.size();
        if (res == max_nodes)
            parse_error(format("regex parsed to more than {} ast nodes", max_nodes));
        const NodeIndex next = res+1;
        m_parsed_regex.nodes.push_back({op, m_ignore_case, next, value, quantifier});
        return res;
    }

    bool at_end() const { return m_pos == m_regex.end(); }

    ParsedRegex::Node& get_node(NodeIndex index)
    {
        return m_parsed_regex.nodes[index];
    }


    [[gnu::noreturn]]
    void parse_error(StringView error) const
    {
        throw regex_error(format("regex parse error: {} at '{}<<<HERE>>>{}'", error,
                                 StringView{m_regex.begin(), m_pos.base()},
                                 StringView{m_pos.base(), m_regex.end()}));
    }

    void validate_lookaround(NodeIndex index)
    {
        for_each_child(m_parsed_regex, index, [this](NodeIndex child_index) {
            auto& child = get_node(child_index);
            if (child.op != ParsedRegex::Literal and child.op != ParsedRegex::Class and
                child.op != ParsedRegex::CharacterType and child.op != ParsedRegex::AnyChar)
                parse_error("Lookaround can only contain literals, any chars or character classes");
            if (child.quantifier.type != ParsedRegex::Quantifier::One)
                parse_error("Quantifiers cannot be used in lookarounds");
            return true;
        });
    }

    ParsedRegex m_parsed_regex;
    StringView m_regex;
    Iterator m_pos;
    bool m_ignore_case = false;

    static constexpr struct CharacterClassEscape {
        Codepoint cp;
        CharacterType ctype;
    } character_class_escapes[] = {
        { 'd', CharacterType::Digit },                { 'D', CharacterType::NotDigit },
        { 'w', CharacterType::Word },                 { 'W', CharacterType::NotWord },
        { 's', CharacterType::Whitespace },           { 'S', CharacterType::NotWhitespace },
        { 'h', CharacterType::HorizontalWhitespace }, { 'H', CharacterType::NotHorizontalWhitespace },
    };

    static constexpr struct ControlEscape {
        Codepoint name;
        Codepoint value;
    } control_escapes[] = {
        { 'f', '\f' },
        { 'n', '\n' },
        { 'r', '\r' },
        { 't', '\t' },
        { 'v', '\v' }
    };
};

constexpr RegexParser::CharacterClassEscape RegexParser::character_class_escapes[];
constexpr RegexParser::ControlEscape RegexParser::control_escapes[];

struct RegexCompiler
{
    RegexCompiler(ParsedRegex&& parsed_regex, RegexCompileFlags flags, MatchDirection direction)
        : m_parsed_regex{parsed_regex}, m_flags(flags), m_forward{direction == MatchDirection::Forward}
    {
        // Approximation of the number of instructions generated
        m_program.instructions.reserve(CompiledRegex::search_prefix_size + parsed_regex.nodes.size() + 1);
        m_program.start_chars = compute_start_chars();

        write_search_prefix();
        compile_node(0);
        push_inst(CompiledRegex::Match);
        m_program.character_classes = std::move(m_parsed_regex.character_classes);
        m_program.save_count = m_parsed_regex.capture_count * 2;
        m_program.direction = direction;
    }

    CompiledRegex get_compiled_regex() { return std::move(m_program); }

private:

    uint32_t compile_node_inner(ParsedRegex::NodeIndex index)
    {
        auto& node = get_node(index);

        const uint32_t start_pos = (uint32_t)m_program.instructions.size();
        const bool ignore_case = node.ignore_case;

        const bool save = (node.op == ParsedRegex::Alternation or node.op == ParsedRegex::Sequence) and
                          (node.value == 0 or (node.value != -1 and not (m_flags & RegexCompileFlags::NoSubs)));
        if (save)
            push_inst(CompiledRegex::Save, node.value * 2 + (m_forward ? 0 : 1));

        Vector<uint32_t> goto_inner_end_offsets;
        switch (node.op)
        {
            case ParsedRegex::Literal:
                if (ignore_case)
                    push_inst(CompiledRegex::Literal_IgnoreCase, to_lower(node.value));
                else
                    push_inst(CompiledRegex::Literal, node.value);
                break;
            case ParsedRegex::AnyChar:
                push_inst(CompiledRegex::AnyChar);
                break;
            case ParsedRegex::Class:
                push_inst(CompiledRegex::Class, node.value);
                break;
            case ParsedRegex::CharacterType:
                push_inst(CompiledRegex::CharacterType, node.value);
                break;
            case ParsedRegex::Sequence:
            {
                if (m_forward)
                    for_each_child(m_parsed_regex, index, [this](ParsedRegex::NodeIndex child) {
                        compile_node(child); return true;
                    });
                else
                    for_each_child_reverse(m_parsed_regex, index, [this](ParsedRegex::NodeIndex  child) {
                        compile_node(child); return true;
                    });
                break;
            }
            case ParsedRegex::Alternation:
            {
                auto split_pos = m_program.instructions.size();
                for_each_child(m_parsed_regex, index, [this, index](ParsedRegex::NodeIndex child) {
                    if (child != index+1)
                        push_inst(CompiledRegex::Split_PrioritizeParent);
                    return true;
                });

                for_each_child(m_parsed_regex, index,
                                  [&, end = node.children_end](ParsedRegex::NodeIndex  child) {
                    auto node = compile_node(child);
                    if (child != index+1)
                        m_program.instructions[split_pos++].param = node;
                    if (get_node(child).children_end != end)
                    {
                        auto jump = push_inst(CompiledRegex::Jump);
                        goto_inner_end_offsets.push_back(jump);
                    }
                    return true;
                });
                break;
            }
            case ParsedRegex::LookAhead:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::LookAhead_IgnoreCase
                                                   : CompiledRegex::LookAhead)
                                    : (ignore_case ? CompiledRegex::LookBehind_IgnoreCase
                                                   : CompiledRegex::LookBehind),
                          push_lookaround(index, false, ignore_case));
                break;
            case ParsedRegex::NegativeLookAhead:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::NegativeLookAhead_IgnoreCase
                                                   : CompiledRegex::NegativeLookAhead)
                                    : (ignore_case ? CompiledRegex::NegativeLookBehind_IgnoreCase
                                                   : CompiledRegex::NegativeLookBehind),
                          push_lookaround(index, false, ignore_case));
                break;
            case ParsedRegex::LookBehind:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::LookBehind_IgnoreCase
                                                   : CompiledRegex::LookBehind)
                                    : (ignore_case ? CompiledRegex::LookAhead_IgnoreCase
                                                   : CompiledRegex::LookAhead),
                          push_lookaround(index, true, ignore_case));
                break;
            case ParsedRegex::NegativeLookBehind:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::NegativeLookBehind_IgnoreCase
                                                   : CompiledRegex::NegativeLookBehind)
                                    : (ignore_case ? CompiledRegex::NegativeLookAhead_IgnoreCase
                                                   : CompiledRegex::NegativeLookAhead),
                          push_lookaround(index, true, ignore_case));
                break;
            case ParsedRegex::LineStart:
                push_inst(m_forward ? CompiledRegex::LineStart
                                    : CompiledRegex::LineEnd);
                break;
            case ParsedRegex::LineEnd:
                push_inst(m_forward ? CompiledRegex::LineEnd
                                    : CompiledRegex::LineStart);
                break;
            case ParsedRegex::WordBoundary:
                push_inst(CompiledRegex::WordBoundary);
                break;
            case ParsedRegex::NotWordBoundary:
                push_inst(CompiledRegex::NotWordBoundary);
                break;
            case ParsedRegex::SubjectBegin:
                push_inst(m_forward ? CompiledRegex::SubjectBegin
                                    : CompiledRegex::SubjectEnd);
                break;
            case ParsedRegex::SubjectEnd:
                push_inst(m_forward ? CompiledRegex::SubjectEnd
                                    : CompiledRegex::SubjectBegin);
                break;
            case ParsedRegex::ResetStart:
                push_inst(CompiledRegex::Save, 0);
                break;
        }

        for (auto& offset : goto_inner_end_offsets)
            m_program.instructions[offset].param = m_program.instructions.size();

        if (save)
            push_inst(CompiledRegex::Save, node.value * 2 + (m_forward ? 1 : 0));

        return start_pos;
    }

    uint32_t compile_node(ParsedRegex::NodeIndex index)
    {
        auto& node = get_node(index);

        const uint32_t start_pos = (uint32_t)m_program.instructions.size();
        Vector<uint32_t> goto_ends;

        auto& quantifier = node.quantifier;

        // TODO reverse, invert the way we write optional quantifiers ?

        if (quantifier.allows_none())
        {
            auto split_pos = push_inst(quantifier.greedy ? CompiledRegex::Split_PrioritizeParent
                                                         : CompiledRegex::Split_PrioritizeChild);
            goto_ends.push_back(split_pos);
        }

        auto inner_pos = compile_node_inner(index);
        // Write the node multiple times when we have a min count quantifier
        for (int i = 1; i < quantifier.min; ++i)
            inner_pos = compile_node_inner(index);

        if (quantifier.allows_infinite_repeat())
            push_inst(quantifier.greedy ? CompiledRegex::Split_PrioritizeChild
                                        : CompiledRegex::Split_PrioritizeParent,
                      inner_pos);

        // Write the node as an optional match for the min -> max counts
        else for (int i = std::max((int16_t)1, quantifier.min); // STILL UGLY !
                  i < quantifier.max; ++i)
        {
            auto split_pos = push_inst(quantifier.greedy ? CompiledRegex::Split_PrioritizeParent
                                                         : CompiledRegex::Split_PrioritizeChild);
            goto_ends.push_back(split_pos);
            compile_node_inner(index);
        }

        for (auto offset : goto_ends)
            m_program.instructions[offset].param = m_program.instructions.size();

        return start_pos;
    }

    // Add an set of instruction prefix used in the search use case
    void write_search_prefix()
    {
        kak_assert(m_program.instructions.empty());
        push_inst(CompiledRegex::Split_PrioritizeChild, CompiledRegex::search_prefix_size);
        push_inst(CompiledRegex::FindNextStart);
        push_inst(CompiledRegex::Split_PrioritizeParent, 1);
        kak_assert(m_program.instructions.size() == CompiledRegex::search_prefix_size);
    }

    uint32_t push_inst(CompiledRegex::Op op, uint32_t param = 0)
    {
        constexpr auto max_instructions = std::numeric_limits<uint16_t>::max();
        uint32_t res = m_program.instructions.size();
        if (res > max_instructions)
            throw regex_error(format("regex compiled to more than {} instructions", max_instructions));
        m_program.instructions.push_back({ op, false, 0, param });
        return res;
    }

    uint32_t push_lookaround(ParsedRegex::NodeIndex index, bool reversed, bool ignore_case)
    {
        uint32_t res = m_program.lookarounds.size();
        auto write_matcher = [this, ignore_case](ParsedRegex::NodeIndex  child) {
                auto& character = get_node(child);
                if (character.op == ParsedRegex::Literal)
                    m_program.lookarounds.push_back(ignore_case ? to_lower(character.value)
                                                                : character.value);
                else if (character.op == ParsedRegex::AnyChar)
                    m_program.lookarounds.push_back(0xF000);
                else if (character.op == ParsedRegex::Class)
                    m_program.lookarounds.push_back(0xF0001 + character.value);
                else if (character.op == ParsedRegex::CharacterType)
                    m_program.lookarounds.push_back(0xF8000 | character.value);
                else
                    kak_assert(false);
                return true;
        };

        if (reversed)
            for_each_child_reverse(m_parsed_regex, index, write_matcher);
        else
            for_each_child(m_parsed_regex, index, write_matcher);

        m_program.lookarounds.push_back((Codepoint)-1);
        return res;
    }

    // Fills accepted and rejected according to which chars can start the given node,
    // returns true if the node did not consume the char, hence a following node in
    // sequence would be still relevant for the parent node start chars computation.
    bool compute_start_chars(ParsedRegex::NodeIndex index,
                             CompiledRegex::StartChars& start_chars) const
    {
        auto& node = get_node(index);
        switch (node.op)
        {
            case ParsedRegex::Literal:
                if (node.value < CompiledRegex::StartChars::count)
                {
                    if (node.ignore_case)
                    {
                        start_chars.map[to_lower(node.value)] = true;
                        start_chars.map[to_upper(node.value)] = true;
                    }
                    else
                        start_chars.map[node.value] = true;
                }
                else
                    start_chars.map[CompiledRegex::StartChars::other] = true;
                return node.quantifier.allows_none();
            case ParsedRegex::AnyChar:
                for (auto& b : start_chars.map)
                    b = true;
                start_chars.map[CompiledRegex::StartChars::other] = true;
                return node.quantifier.allows_none();
            case ParsedRegex::Class:
            {
                auto& character_class = m_parsed_regex.character_classes[node.value];
                for (Codepoint cp = 0; cp < CompiledRegex::StartChars::count; ++cp)
                {
                    if (is_character_class(character_class, cp))
                        start_chars.map[cp] = true;
                }
                start_chars.map[CompiledRegex::StartChars::other] = true;<commit_msg>Regex: Various small code tweaks<commit_after>#include "regex_impl.hh"

#include "exception.hh"
#include "string.hh"
#include "unicode.hh"
#include "unit_tests.hh"
#include "utf8.hh"
#include "utf8_iterator.hh"
#include "string_utils.hh"
#include "vector.hh"

#include <cstring> 

namespace Kakoune
{

constexpr Codepoint CompiledRegex::StartChars::other;

struct ParsedRegex
{
    enum Op : char
    {
        Literal,
        AnyChar,
        Class,
        CharacterType,
        Sequence,
        Alternation,
        LineStart,
        LineEnd,
        WordBoundary,
        NotWordBoundary,
        SubjectBegin,
        SubjectEnd,
        ResetStart,
        LookAhead,
        NegativeLookAhead,
        LookBehind,
        NegativeLookBehind,
    };

    struct Quantifier
    {
        enum Type : char
        {
            One,
            Optional,
            RepeatZeroOrMore,
            RepeatOneOrMore,
            RepeatMinMax,
        };
        Type type = One;
        bool greedy = true;
        int16_t min = -1, max = -1;

        bool allows_none() const
        {
            return type == Quantifier::Optional or
                   type == Quantifier::RepeatZeroOrMore or
                  (type == Quantifier::RepeatMinMax and min <= 0);
        }

        bool allows_infinite_repeat() const
        {
            return type == Quantifier::RepeatZeroOrMore or
                   type == Quantifier::RepeatOneOrMore or
                  (type == Quantifier::RepeatMinMax and max < 0);
        };
    };

    struct Node;
    using NodeIndex = uint16_t;

    struct Node
    {
        Op op;
        bool ignore_case;
        NodeIndex children_end;
        Codepoint value;
        Quantifier quantifier;
    };
    static_assert(sizeof(Node) == 16, "");

    Vector<Node, MemoryDomain::Regex> nodes;

    Vector<CharacterClass, MemoryDomain::Regex> character_classes;
    size_t capture_count;
};

namespace
{
template<typename Func>
bool for_each_child(const ParsedRegex& parsed_regex, ParsedRegex::NodeIndex index, Func&& func)
{
    const auto end = parsed_regex.nodes[index].children_end;
    for (auto child = index+1; child != end;
         child = parsed_regex.nodes[child].children_end)
    {
        if (func(child) == false)
            return false;
    }
    return true;
}

template<typename Func>
bool for_each_child_reverse(const ParsedRegex& parsed_regex, ParsedRegex::NodeIndex index, Func&& func)
{
    auto find_last_child = [&](ParsedRegex::NodeIndex begin, ParsedRegex::NodeIndex end) {
        while (parsed_regex.nodes[begin].children_end != end)
            begin = parsed_regex.nodes[begin].children_end;
        return begin;
    };
    const auto first_child = index+1;
    auto end = parsed_regex.nodes[index].children_end;
    while (end != first_child)
    {
        auto child = find_last_child(first_child, end);
        if (func(child) == false)
            return false;
        end = child;
    }
    return true;
}
}

// Recursive descent parser based on naming used in the ECMAScript
// standard, although the syntax is not fully compatible.
struct RegexParser
{
    RegexParser(StringView re)
        : m_regex{re}, m_pos{re.begin(), re}
    {
        m_parsed_regex.capture_count = 1;
        m_parsed_regex.nodes.reserve((size_t)re.length());
        NodeIndex root = disjunction(0);
        kak_assert(root == 0);
    }

    ParsedRegex get_parsed_regex() { return std::move(m_parsed_regex); }

    static ParsedRegex parse(StringView re) { return RegexParser{re}.get_parsed_regex(); }

private:
    struct InvalidPolicy
    {
        Codepoint operator()(Codepoint cp) { throw regex_error{"Invalid utf8 in regex"}; }
    };

    using Iterator = utf8::iterator<const char*, Codepoint, int, InvalidPolicy>;
    using NodeIndex = ParsedRegex::NodeIndex;

    NodeIndex disjunction(unsigned capture = -1)
    {
        NodeIndex index = new_node(ParsedRegex::Alternation);
        get_node(index).value = capture;
        while (true)
        {
            alternative();
            if (at_end() or *m_pos != '|')
                break;
            ++m_pos;
        }
        get_node(index).children_end = m_parsed_regex.nodes.size();

        return index;
    }

    NodeIndex alternative(ParsedRegex::Op op = ParsedRegex::Sequence)
    {
        NodeIndex index = new_node(op);
        while (auto t = term())
        {}
        get_node(index).children_end = m_parsed_regex.nodes.size();

        return index;
    }

    Optional<NodeIndex> term()
    {
        while (modifiers()) // read all modifiers
        {}
        if (auto node = assertion())
            return node;
        if (auto node = atom())
        {
            get_node(*node).quantifier = quantifier();
            return node;
        }
        return {};
    }

    bool accept(StringView expected)
    {
        auto it = m_pos.base();
        for (auto expected_it = expected.begin(); expected_it != expected.end(); ++expected_it)
        {
            if (it == m_regex.end() or *it++ != *expected_it)
                return false;
        }
        m_pos = Iterator{it, m_regex};
        return true;
    }

    bool modifiers()
    {
        if (accept("(?i)"))
        {
            m_ignore_case = true;
            return true;
        }
        if (accept("(?I)"))
        {
            m_ignore_case = false;
            return true;
        }
        return false;
    }

    Optional<NodeIndex> assertion()
    {
        if (at_end())
            return {};

        switch (*m_pos)
        {
            case '^': ++m_pos; return new_node(ParsedRegex::LineStart);
            case '$': ++m_pos; return new_node(ParsedRegex::LineEnd);
            case '\\':
                if (m_pos+1 == m_regex.end())
                    return {};
                switch (*(m_pos+1))
                {
                    case 'b': m_pos += 2; return new_node(ParsedRegex::WordBoundary);
                    case 'B': m_pos += 2; return new_node(ParsedRegex::NotWordBoundary);
                    case 'A': m_pos += 2; return new_node(ParsedRegex::SubjectBegin);
                    case 'z': m_pos += 2; return new_node(ParsedRegex::SubjectEnd);
                    case 'K': m_pos += 2; return new_node(ParsedRegex::ResetStart);
                }
                break;
            case '(':
            {
                Optional<ParsedRegex::Op> lookaround_op;
                constexpr struct { StringView prefix; ParsedRegex::Op op; } lookarounds[] = {
                    { "(?=", ParsedRegex::LookAhead },
                    { "(?!", ParsedRegex::NegativeLookAhead },
                    { "(?<=", ParsedRegex::LookBehind },
                    { "(?<!", ParsedRegex::NegativeLookBehind }
                };
                for (auto& lookaround : lookarounds)
                {
                    if (accept(lookaround.prefix))
                    {
                        lookaround_op = lookaround.op;
                        break;
                    }
                }
                if (not lookaround_op)
                        return {};

                NodeIndex lookaround = alternative(*lookaround_op);
                if (at_end() or *m_pos++ != ')')
                    parse_error("unclosed parenthesis");

                validate_lookaround(lookaround);
                return lookaround;
            }
        }
        return {};
    }

    Optional<NodeIndex> atom()
    {
        if (at_end())
            return {};

        const Codepoint cp = *m_pos;
        switch (cp)
        {
            case '.': ++m_pos; return new_node(ParsedRegex::AnyChar);
            case '(':
            {
                ++m_pos;
                const bool capture = not accept("?:");
                NodeIndex content = disjunction(capture ? m_parsed_regex.capture_count++ : -1);
                if (at_end() or *m_pos++ != ')')
                    parse_error("unclosed parenthesis");
                return content;
            }
            case '\\':
                ++m_pos;
                return atom_escape();
            case '[':
                ++m_pos;
                return character_class();
            case '|': case ')':
                return {};
            default:
                if (contains("^$.*+?[]{}", cp))
                    parse_error(format("unexpected '{}'", cp));
                ++m_pos;
                return new_node(ParsedRegex::Literal, cp);
        }
    }

    NodeIndex atom_escape()
    {
        const Codepoint cp = *m_pos++;

        if (cp == 'Q')
        {
            auto escaped_sequence = new_node(ParsedRegex::Sequence);
            constexpr StringView end_mark{"\\E"};

            auto quote_end = std::search(m_pos.base(), m_regex.end(), end_mark.begin(), end_mark.end());
            while (m_pos != quote_end)
                new_node(ParsedRegex::Literal, *m_pos++);
            get_node(escaped_sequence).children_end = m_parsed_regex.nodes.size();

            if (quote_end != m_regex.end())
                m_pos += 2;

            return escaped_sequence;
        }

        // CharacterClassEscape
        auto class_it = find_if(character_class_escapes, [cp](auto& c) { return c.cp == cp; });
        if (class_it != std::end(character_class_escapes))
            return new_node(ParsedRegex::CharacterType, (Codepoint)class_it->ctype);

        // CharacterEscape
        for (auto& control : control_escapes)
        {
            if (control.name == cp)
                return new_node(ParsedRegex::Literal, control.value);
        }

        auto read_hex = [this](size_t count)
        {
            Codepoint res = 0;
            for (int i = 0; i < count; ++i)
            {
                if (at_end())
                    parse_error("unterminated hex sequence");
                Codepoint digit = *m_pos++;
                Codepoint digit_value;
                if ('0' <= digit and digit <= '9')
                    digit_value = digit - '0';
                else if ('a' <= digit and digit <= 'f')
                    digit_value = 0xa + digit - 'a';
                else if ('A' <= digit and digit <= 'F')
                    digit_value = 0xa + digit - 'A';
                else
                    parse_error(format("invalid hex digit '{}'", digit));

                res = res * 16 + digit_value;
            }
            return res;
        };

        if (cp == '0')
            return new_node(ParsedRegex::Literal, '\0');
        else if (cp == 'c')
        {
            if (at_end())
                parse_error("unterminated control escape");
            Codepoint ctrl = *m_pos++;
            if (('a' <= ctrl and ctrl <= 'z') or ('A' <= ctrl and ctrl <= 'Z'))
                return new_node(ParsedRegex::Literal, ctrl % 32);
            parse_error(format("Invalid control escape character '{}'", ctrl));
        }
        else if (cp == 'x')
            return new_node(ParsedRegex::Literal, read_hex(2));
        else if (cp == 'u')
            return new_node(ParsedRegex::Literal, read_hex(4));

        if (contains("^$\\.*+?()[]{}|", cp)) // SyntaxCharacter
            return new_node(ParsedRegex::Literal, cp);
        parse_error(format("unknown atom escape '{}'", cp));
    }

    void normalize_ranges(Vector<CharacterClass::Range, MemoryDomain::Regex>& ranges)
    {
        if (ranges.empty())
            return;

        // Sort ranges so that we can use binary search
        std::sort(ranges.begin(), ranges.end(),
                  [](auto& lhs, auto& rhs) { return lhs.min < rhs.min; });

        // merge overlapping ranges 
        auto pos = ranges.begin();
        for (auto next = pos+1; next != ranges.end(); ++next)
        {
            if (pos->max + 1 >= next->min)
            {
                if (next->max > pos->max)
                    pos->max = next->max;
            }
            else
                *++pos = *next;
        }
        ranges.erase(pos+1, ranges.end());
    }

    NodeIndex character_class()
    {
        CharacterClass character_class;

        character_class.ignore_case = m_ignore_case;
        character_class.negative = m_pos != m_regex.end() and *m_pos == '^';
        if (character_class.negative)
            ++m_pos;

        while (m_pos != m_regex.end() and *m_pos != ']')
        {
            auto cp = *m_pos++;
            if (cp == '-')
            {
                character_class.ranges.push_back({ '-', '-' });
                continue;
            }

            if (at_end())
                break;

            if (cp == '\\')
            {
                auto it = find_if(character_class_escapes,
                                  [cp = *m_pos](auto& t) { return t.cp == cp; });
                if (it != std::end(character_class_escapes))
                {
                    character_class.ctypes |= it->ctype;
                    ++m_pos;
                    continue;
                }
                else // its just an escaped character
                {
                    cp = *m_pos++;
                    for (auto& control : control_escapes)
                    {
                        if (control.name == cp)
                        {
                            cp = control.value;
                            break;
                        }
                    }
                }
            }

            CharacterClass::Range range = { cp, cp };
            if (*m_pos == '-')
            {
                if (++m_pos == m_regex.end())
                    break;
                if (*m_pos != ']')
                {
                    range.max = *m_pos++;
                    if (range.min > range.max)
                        parse_error("invalid range specified");
                }
                else
                {
                    character_class.ranges.push_back(range);
                    range = { '-', '-' };
                }
            }
            character_class.ranges.push_back(range);
        }
        if (at_end())
            parse_error("unclosed character class");
        ++m_pos;

        if (m_ignore_case)
        {
            for (auto& range : character_class.ranges)
            {
                range.min = to_lower(range.min);
                range.max = to_lower(range.max);
            }
        }

        normalize_ranges(character_class.ranges);

        // Optimize the relatively common case of using a character class to
        // escape a character, such as [*]
        if (character_class.ctypes == CharacterType::None and not character_class.negative and
            character_class.ranges.size() == 1 and
            character_class.ranges.front().min == character_class.ranges.front().max)
            return new_node(ParsedRegex::Literal, character_class.ranges.front().min);

        if (character_class.ctypes != CharacterType::None and not character_class.negative and
            character_class.ranges.empty())
            return new_node(ParsedRegex::CharacterType, (Codepoint)character_class.ctypes);

        auto class_id = m_parsed_regex.character_classes.size();
        m_parsed_regex.character_classes.push_back(std::move(character_class));

        return new_node(ParsedRegex::Class, class_id);
    }

    ParsedRegex::Quantifier quantifier()
    {
        if (at_end())
            return {ParsedRegex::Quantifier::One};

        constexpr int max_repeat = 1000;
        auto read_bound = [&]() {
            int16_t res = 0;
            for (auto begin = m_pos; m_pos != m_regex.end(); ++m_pos)
            {
                const auto cp = *m_pos;
                if (cp < '0' or cp > '9')
                    return m_pos == begin ? (int16_t)-1 : res;
                res = res * 10 + cp - '0';
                if (res > max_repeat)
                    parse_error(format("Explicit quantifier is too big, maximum is {}", max_repeat));
            }
            return res;
        };

        auto check_greedy = [&]() {
            if (at_end() or *m_pos != '?')
                return true;
            ++m_pos;
            return false;
        };

        switch (*m_pos)
        {
            case '*': ++m_pos; return {ParsedRegex::Quantifier::RepeatZeroOrMore, check_greedy()};
            case '+': ++m_pos; return {ParsedRegex::Quantifier::RepeatOneOrMore, check_greedy()};
            case '?': ++m_pos; return {ParsedRegex::Quantifier::Optional, check_greedy()};
            case '{':
            {
                ++m_pos;
                const int16_t min = read_bound();
                int16_t max = min;
                if (*m_pos == ',')
                {
                    ++m_pos;
                    max = read_bound();
                }
                if (*m_pos++ != '}')
                   parse_error("expected closing bracket");
                return {ParsedRegex::Quantifier::RepeatMinMax, check_greedy(), min, max};
            }
            default: return {ParsedRegex::Quantifier::One};
        }
    }

    NodeIndex new_node(ParsedRegex::Op op, Codepoint value = -1,
                          ParsedRegex::Quantifier quantifier = {ParsedRegex::Quantifier::One})
    {
        constexpr auto max_nodes = std::numeric_limits<uint16_t>::max();
        const NodeIndex res = m_parsed_regex.nodes.size();
        if (res == max_nodes)
            parse_error(format("regex parsed to more than {} ast nodes", max_nodes));
        const NodeIndex next = res+1;
        m_parsed_regex.nodes.push_back({op, m_ignore_case, next, value, quantifier});
        return res;
    }

    bool at_end() const { return m_pos == m_regex.end(); }

    ParsedRegex::Node& get_node(NodeIndex index)
    {
        return m_parsed_regex.nodes[index];
    }


    [[gnu::noreturn]]
    void parse_error(StringView error) const
    {
        throw regex_error(format("regex parse error: {} at '{}<<<HERE>>>{}'", error,
                                 StringView{m_regex.begin(), m_pos.base()},
                                 StringView{m_pos.base(), m_regex.end()}));
    }

    void validate_lookaround(NodeIndex index)
    {
        for_each_child(m_parsed_regex, index, [this](NodeIndex child_index) {
            auto& child = get_node(child_index);
            if (child.op != ParsedRegex::Literal and child.op != ParsedRegex::Class and
                child.op != ParsedRegex::CharacterType and child.op != ParsedRegex::AnyChar)
                parse_error("Lookaround can only contain literals, any chars or character classes");
            if (child.quantifier.type != ParsedRegex::Quantifier::One)
                parse_error("Quantifiers cannot be used in lookarounds");
            return true;
        });
    }

    ParsedRegex m_parsed_regex;
    StringView m_regex;
    Iterator m_pos;
    bool m_ignore_case = false;

    static constexpr struct CharacterClassEscape {
        Codepoint cp;
        CharacterType ctype;
    } character_class_escapes[] = {
        { 'd', CharacterType::Digit },                { 'D', CharacterType::NotDigit },
        { 'w', CharacterType::Word },                 { 'W', CharacterType::NotWord },
        { 's', CharacterType::Whitespace },           { 'S', CharacterType::NotWhitespace },
        { 'h', CharacterType::HorizontalWhitespace }, { 'H', CharacterType::NotHorizontalWhitespace },
    };

    static constexpr struct ControlEscape {
        Codepoint name;
        Codepoint value;
    } control_escapes[] = {
        { 'f', '\f' },
        { 'n', '\n' },
        { 'r', '\r' },
        { 't', '\t' },
        { 'v', '\v' }
    };
};

constexpr RegexParser::CharacterClassEscape RegexParser::character_class_escapes[];
constexpr RegexParser::ControlEscape RegexParser::control_escapes[];

struct RegexCompiler
{
    RegexCompiler(ParsedRegex&& parsed_regex, RegexCompileFlags flags, MatchDirection direction)
        : m_parsed_regex{parsed_regex}, m_flags(flags), m_forward{direction == MatchDirection::Forward}
    {
        // Approximation of the number of instructions generated
        m_program.instructions.reserve(CompiledRegex::search_prefix_size + parsed_regex.nodes.size() + 1);
        m_program.start_chars = compute_start_chars();

        write_search_prefix();
        compile_node(0);
        push_inst(CompiledRegex::Match);
        m_program.character_classes = std::move(m_parsed_regex.character_classes);
        m_program.save_count = m_parsed_regex.capture_count * 2;
        m_program.direction = direction;
    }

    CompiledRegex get_compiled_regex() { return std::move(m_program); }

private:

    uint32_t compile_node_inner(ParsedRegex::NodeIndex index)
    {
        auto& node = get_node(index);

        const uint32_t start_pos = (uint32_t)m_program.instructions.size();
        const bool ignore_case = node.ignore_case;

        const bool save = (node.op == ParsedRegex::Alternation or node.op == ParsedRegex::Sequence) and
                          (node.value == 0 or (node.value != -1 and not (m_flags & RegexCompileFlags::NoSubs)));
        if (save)
            push_inst(CompiledRegex::Save, node.value * 2 + (m_forward ? 0 : 1));

        Vector<uint32_t> goto_inner_end_offsets;
        switch (node.op)
        {
            case ParsedRegex::Literal:
                if (ignore_case)
                    push_inst(CompiledRegex::Literal_IgnoreCase, to_lower(node.value));
                else
                    push_inst(CompiledRegex::Literal, node.value);
                break;
            case ParsedRegex::AnyChar:
                push_inst(CompiledRegex::AnyChar);
                break;
            case ParsedRegex::Class:
                push_inst(CompiledRegex::Class, node.value);
                break;
            case ParsedRegex::CharacterType:
                push_inst(CompiledRegex::CharacterType, node.value);
                break;
            case ParsedRegex::Sequence:
            {
                if (m_forward)
                    for_each_child(m_parsed_regex, index, [this](ParsedRegex::NodeIndex child) {
                        compile_node(child); return true;
                    });
                else
                    for_each_child_reverse(m_parsed_regex, index, [this](ParsedRegex::NodeIndex  child) {
                        compile_node(child); return true;
                    });
                break;
            }
            case ParsedRegex::Alternation:
            {
                auto split_pos = m_program.instructions.size();
                for_each_child(m_parsed_regex, index, [this, index](ParsedRegex::NodeIndex child) {
                    if (child != index+1)
                        push_inst(CompiledRegex::Split_PrioritizeParent);
                    return true;
                });

                for_each_child(m_parsed_regex, index,
                                  [&, end = node.children_end](ParsedRegex::NodeIndex  child) {
                    auto node = compile_node(child);
                    if (child != index+1)
                        m_program.instructions[split_pos++].param = node;
                    if (get_node(child).children_end != end)
                    {
                        auto jump = push_inst(CompiledRegex::Jump);
                        goto_inner_end_offsets.push_back(jump);
                    }
                    return true;
                });
                break;
            }
            case ParsedRegex::LookAhead:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::LookAhead_IgnoreCase
                                                   : CompiledRegex::LookAhead)
                                    : (ignore_case ? CompiledRegex::LookBehind_IgnoreCase
                                                   : CompiledRegex::LookBehind),
                          push_lookaround(index, false, ignore_case));
                break;
            case ParsedRegex::NegativeLookAhead:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::NegativeLookAhead_IgnoreCase
                                                   : CompiledRegex::NegativeLookAhead)
                                    : (ignore_case ? CompiledRegex::NegativeLookBehind_IgnoreCase
                                                   : CompiledRegex::NegativeLookBehind),
                          push_lookaround(index, false, ignore_case));
                break;
            case ParsedRegex::LookBehind:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::LookBehind_IgnoreCase
                                                   : CompiledRegex::LookBehind)
                                    : (ignore_case ? CompiledRegex::LookAhead_IgnoreCase
                                                   : CompiledRegex::LookAhead),
                          push_lookaround(index, true, ignore_case));
                break;
            case ParsedRegex::NegativeLookBehind:
                push_inst(m_forward ? (ignore_case ? CompiledRegex::NegativeLookBehind_IgnoreCase
                                                   : CompiledRegex::NegativeLookBehind)
                                    : (ignore_case ? CompiledRegex::NegativeLookAhead_IgnoreCase
                                                   : CompiledRegex::NegativeLookAhead),
                          push_lookaround(index, true, ignore_case));
                break;
            case ParsedRegex::LineStart:
                push_inst(m_forward ? CompiledRegex::LineStart
                                    : CompiledRegex::LineEnd);
                break;
            case ParsedRegex::LineEnd:
                push_inst(m_forward ? CompiledRegex::LineEnd
                                    : CompiledRegex::LineStart);
                break;
            case ParsedRegex::WordBoundary:
                push_inst(CompiledRegex::WordBoundary);
                break;
            case ParsedRegex::NotWordBoundary:
                push_inst(CompiledRegex::NotWordBoundary);
                break;
            case ParsedRegex::SubjectBegin:
                push_inst(m_forward ? CompiledRegex::SubjectBegin
                                    : CompiledRegex::SubjectEnd);
                break;
            case ParsedRegex::SubjectEnd:
                push_inst(m_forward ? CompiledRegex::SubjectEnd
                                    : CompiledRegex::SubjectBegin);
                break;
            case ParsedRegex::ResetStart:
                push_inst(CompiledRegex::Save, 0);
                break;
        }

        for (auto& offset : goto_inner_end_offsets)
            m_program.instructions[offset].param = m_program.instructions.size();

        if (save)
            push_inst(CompiledRegex::Save, node.value * 2 + (m_forward ? 1 : 0));

        return start_pos;
    }

    uint32_t compile_node(ParsedRegex::NodeIndex index)
    {
        auto& node = get_node(index);

        const uint32_t start_pos = (uint32_t)m_program.instructions.size();
        Vector<uint32_t> goto_ends;

        auto& quantifier = node.quantifier;

        // TODO reverse, invert the way we write optional quantifiers ?

        if (quantifier.allows_none())
        {
            auto split_pos = push_inst(quantifier.greedy ? CompiledRegex::Split_PrioritizeParent
                                                         : CompiledRegex::Split_PrioritizeChild);
            goto_ends.push_back(split_pos);
        }

        auto inner_pos = compile_node_inner(index);
        // Write the node multiple times when we have a min count quantifier
        for (int i = 1; i < quantifier.min; ++i)
            inner_pos = compile_node_inner(index);

        if (quantifier.allows_infinite_repeat())
            push_inst(quantifier.greedy ? CompiledRegex::Split_PrioritizeChild
                                        : CompiledRegex::Split_PrioritizeParent,
                      inner_pos);

        // Write the node as an optional match for the min -> max counts
        else for (int i = std::max((int16_t)1, quantifier.min); // STILL UGLY !
                  i < quantifier.max; ++i)
        {
            auto split_pos = push_inst(quantifier.greedy ? CompiledRegex::Split_PrioritizeParent
                                                         : CompiledRegex::Split_PrioritizeChild);
            goto_ends.push_back(split_pos);
            compile_node_inner(index);
        }

        for (auto offset : goto_ends)
            m_program.instructions[offset].param = m_program.instructions.size();

        return start_pos;
    }

    // Add an set of instruction prefix used in the search use case
    void write_search_prefix()
    {
        kak_assert(m_program.instructions.empty());
        push_inst(CompiledRegex::Split_PrioritizeChild, CompiledRegex::search_prefix_size);
        push_inst(CompiledRegex::FindNextStart);
        push_inst(CompiledRegex::Split_PrioritizeParent, 1);
        kak_assert(m_program.instructions.size() == CompiledRegex::search_prefix_size);
    }

    uint32_t push_inst(CompiledRegex::Op op, uint32_t param = 0)
    {
        constexpr auto max_instructions = std::numeric_limits<uint16_t>::max();
        uint32_t res = m_program.instructions.size();
        if (res > max_instructions)
            throw regex_error(format("regex compiled to more than {} instructions", max_instructions));
        m_program.instructions.push_back({ op, false, 0, param });
        return res;
    }

    uint32_t push_lookaround(ParsedRegex::NodeIndex index, bool reversed, bool ignore_case)
    {
        uint32_t res = m_program.lookarounds.size();
        auto write_matcher = [this, ignore_case](ParsedRegex::NodeIndex  child) {
                auto& character = get_node(child);
                if (character.op == ParsedRegex::Literal)
                    m_program.lookarounds.push_back(ignore_case ? to_lower(character.value)
                                                                : character.value);
                else if (character.op == ParsedRegex::AnyChar)
                    m_program.lookarounds.push_back(0xF000);
                else if (character.op == ParsedRegex::Class)
                    m_program.lookarounds.push_back(0xF0001 + character.value);
                else if (character.op == ParsedRegex::CharacterType)
                    m_program.lookarounds.push_back(0xF8000 | character.value);
                else
                    kak_assert(false);
                return true;
        };

        if (reversed)
            for_each_child_reverse(m_parsed_regex, index, write_matcher);
        else
            for_each_child(m_parsed_regex, index, write_matcher);

        m_program.lookarounds.push_back((Codepoint)-1);
        return res;
    }

    // Fills accepted and rejected according to which chars can start the given node,
    // returns true if the node did not consume the char, hence a following node in
    // sequence would be still relevant for the parent node start chars computation.
    bool compute_start_chars(ParsedRegex::NodeIndex index,
                             CompiledRegex::StartChars& start_chars) const
    {
        auto& node = get_node(index);
        switch (node.op)
        {
            case ParsedRegex::Literal:
                if (node.value < CompiledRegex::StartChars::count)
                {
                    if (node.ignore_case)
                    {
                        start_chars.map[to_lower(node.value)] = true;
                        start_chars.map[to_upper(node.value)] = true;
                    }
                    else
                        start_chars.map[node.value] = true;
                }
                else
                    start_chars.map[CompiledRegex::StartChars::other] = true;
                return node.quantifier.allows_none();
            case ParsedRegex::AnyChar:
                for (auto& b : start_chars.map)
                    b = true;
               return node.quantifier.allows_none();
            case ParsedRegex::Class:
            {
                auto& character_class = m_parsed_regex.character_classes[node.value];
                for (Codepoint cp = 0; cp < CompiledRegex::StartChars::count; ++cp)
                {
                    if (is_character_class(character_class, cp))
                        start_chars.map[cp] = true;
                }
                start_chars.map[CompiledRegex::StartChars::other] = true;
{'fraction_non_alphanumeric': 0.10649146589438659, 'fraction_numerical': 0.004174625670096741, 'mean_word_length': 1.625030327537404, 'pattern_counts': {'":': 0, '<': 81, '<?xml version=': 0, '>': 69, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 72, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4501489', 'n_tokens_mistral': 18177, 'n_tokens_neox': 17352, 'n_words': 3559}