ClickHouse

1
#include <Functions/checkHyperscanRegexp.h>
2

3
#include <Common/Exception.h>
4
#include <charconv>
5

6
namespace DB
7
{
8
namespace ErrorCodes
9
{
10
    extern const int BAD_ARGUMENTS;
11
}
12

13
void checkHyperscanRegexp(const std::vector<std::string_view> & regexps, size_t max_hyperscan_regexp_length, size_t max_hyperscan_regexp_total_length)
14
{
15
    if (max_hyperscan_regexp_length > 0 || max_hyperscan_regexp_total_length > 0)
16
    {
17
        size_t total_regexp_length = 0;
18
        for (const auto & regexp : regexps)
19
        {
20
            if (max_hyperscan_regexp_length > 0 && regexp.size() > max_hyperscan_regexp_length)
21
                throw Exception(ErrorCodes::BAD_ARGUMENTS, "Regexp length too large ({} > {})", regexp.size(), max_hyperscan_regexp_length);
22
            total_regexp_length += regexp.size();
23
        }
24

25
        if (max_hyperscan_regexp_total_length > 0 && total_regexp_length > max_hyperscan_regexp_total_length)
26
            throw Exception(ErrorCodes::BAD_ARGUMENTS, "Total regexp lengths too large ({} > {})",
27
                            total_regexp_length, max_hyperscan_regexp_total_length);
28
    }
29
}
30

31
namespace
32
{
33

34
bool isLargerThanFifty(std::string_view str)
35
{
36
    int number;
37
    auto [_, ec] = std::from_chars(str.begin(), str.end(), number);
38
    if (ec != std::errc())
39
        return false;
40
    return number > 50;
41
}
42

43
}
44

45
/// Check for sub-patterns of the form x{n} or x{n,} can be expensive. Ignore spaces before/after n and m.
46
bool SlowWithHyperscanChecker::isSlowOneRepeat(std::string_view regexp)
47
{
48
    std::string_view haystack(regexp.data(), regexp.size());
49
    std::string_view matches[2];
50
    size_t start_pos = 0;
51
    while (start_pos < haystack.size())
52
    {
53
        if (searcher_one_repeat.Match(haystack, start_pos, haystack.size(), re2::RE2::Anchor::UNANCHORED, matches, 2))
54
        {
55
            const auto & match = matches[0];
56
            start_pos = (matches[0].data() - haystack.data()) + match.size(); // new start pos = prefix before match + match length
57
            const auto & submatch = matches[1];
58
            if (isLargerThanFifty({submatch.data(), submatch.size()}))
59
                return true;
60
        }
61
        else
62
            break;
63
    }
64
    return false;
65
}
66

67
/// Check if sub-patterns of the form x{n,m} can be expensive. Ignore spaces before/after n and m.
68
bool SlowWithHyperscanChecker::isSlowTwoRepeats(std::string_view regexp)
69
{
70
    std::string_view haystack(regexp.data(), regexp.size());
71
    std::string_view matches[3];
72
    size_t start_pos = 0;
73
    while (start_pos < haystack.size())
74
    {
75
        if (searcher_two_repeats.Match(haystack, start_pos, haystack.size(), re2::RE2::Anchor::UNANCHORED, matches, 3))
76
        {
77
            const auto & match = matches[0];
78
            start_pos = (matches[0].data() - haystack.data()) + match.size(); // new start pos = prefix before match + match length
79
            const auto & submatch1 = matches[1];
80
            const auto & submatch2 = matches[2];
81
            if (isLargerThanFifty({submatch1.data(), submatch1.size()})
82
             || isLargerThanFifty({submatch2.data(), submatch2.size()}))
83
                return true;
84
        }
85
        else
86
            break;
87
    }
88
    return false;
89
}
90

91
SlowWithHyperscanChecker::SlowWithHyperscanChecker()
92
    : searcher_one_repeat(R"(\{\s*([\d]+)\s*,?\s*})")
93
    , searcher_two_repeats(R"(\{\s*([\d]+)\s*,\s*([\d]+)\s*\})")
94
{}
95

96
bool SlowWithHyperscanChecker::isSlow(std::string_view regexp)
97
{
98
    if (isSlowOneRepeat(regexp))
99
        return true;
100
    else if (isSlowTwoRepeats(regexp))
101
        return true;
102
    return false;
103
}
104

105
}
106