github-actions[bot] commented on code in PR #67538:
URL: https://github.com/apache/doris/pull/67538#discussion_r4000191029
##########
be/src/storage/index/snii/snii_index_reader.cpp:
##########
@@ -156,6 +164,27 @@ bool uses_phrase_frequency_scoring(InvertedIndexQueryType
query_type,
query_type == InvertedIndexQueryType::MATCH_PHRASE_PREFIX_QUERY);
}
+// Query types whose answer is decided by terms the current analyzer produced.
On a
+// gram-family index those terms are grams, and they only mean what the
segment's own grams
+// mean when both were cut by the same scheme. MATCH_REGEXP belongs here even
though its
+// pattern is raw: the scalar function matches that pattern against the terms
the current
+// analyzer cuts each row into, while the index matches it against the
persisted dictionary,
+// so the two answer the same question only when both were cut alike. A gram
query compiles
+// against the segment's own scheme, so it is not affected.
+bool analyzes_query_terms(InvertedIndexQueryType query_type) {
+ switch (query_type) {
+ case InvertedIndexQueryType::MATCH_ANY_QUERY:
Review Comment:
[P1] Include analyzer-requiring `EQUAL_QUERY` in this gram-scheme fence.
SNII SEARCH maps default/`or` TERM (and EXACT) to EQUAL, passes the current
analyzer context, and `_parse_query_terms()` therefore cuts the value with the
current policy. After same-name policy recovery, those grams are looked up in
the old segment dictionary: for example, a dense-3 segment containing `abcdef`
has `abc,bcd,cde,def`, while recovered dense-4 TERM `abcdef` looks up
`abcd,bcde,cdef` and returns an empty exact bitmap. SEARCH has no scalar
fallback/recheck, and this omission also leaves the scheme-blind result cache
enabled. Please fence/cache-exclude analyzed EQUAL and cover SEARCH TERM/EXACT
across policy recreation.
##########
be/src/storage/index/inverted/gram/regex_ast.cpp:
##########
@@ -0,0 +1,813 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "storage/index/inverted/gram/regex_ast.h"
+
+#include <algorithm>
+#include <cctype>
+#include <cstdint>
+
+namespace doris::segment_v2::gram {
+
+// The BE storage target enables CMake unity builds (several .cpp files are
compiled together,
+// see UNITY_BUILD_BATCH_SIZE in be/src/storage/CMakeLists.txt), so every
anonymous namespace in
+// a batch is merged into one translation unit. A bare anonymous namespace
then redefines any
+// symbol whose name another file of the same batch happens to reuse (even in
a different .cpp),
+// and the batching changes as files are added to or removed from the
directory, so "this batch
+// only holds these files" cannot be assumed for long. Hence the extra named
namespace private
+// to this file, which isolates this file's anonymous namespace; the symbols
inside it still
+// have internal linkage (anonymous-namespace semantics are unaffected by a
named enclosing
+// namespace).
+namespace regex_ast_detail {
+
+namespace {
+
+// Maximum recursion nesting depth of `(...)` groups: every extra group level
adds one more
+// recursion through the parse_alt/parse_cat/parse_atom call chain. A
malformed (or maliciously
+// crafted) regex can drive that chain very deep with a pile of nested
parentheses and blow the
+// stack; this repository has already seen a stack overflow from deep
recursion (CIR-21633), so
+// there is a hard cap here that errors out instead of recursing further.
+constexpr int kMaxNestingDepth = 64;
+
+// The parser derives conservative literal constraints for the scalar regex
engines.
+// Unsupported syntax fails parsing so the caller can skip gram filtering.
+
+// Infer the byte length of a UTF-8 sequence from its lead byte; an illegal
lead byte counts as a
+// single byte.
+int utf8_len(unsigned char c) {
+ if (c < 0x80) {
+ return 1;
+ }
+ if ((c >> 5) == 0x6) {
+ return 2;
+ }
+ if ((c >> 4) == 0xE) {
+ return 3;
+ }
+ if ((c >> 3) == 0x1E) {
+ return 4;
+ }
+ return 1; // illegal lead byte: treat it as a single byte
+}
+
+// The largest legal Unicode code point. Anything above it can only be a fake
code point minted
+// by decode_one_cp for an ill-formed byte, and must never reach encode_cp:
the four-byte sequence
+// encode_cp would produce encodes a value above U+10FFFF, so it is a byte
string no encoder can
+// emit and no index can hold, and demanding it as a gram would filter every
row away.
+constexpr uint32_t kMaxCodePoint = 0x10FFFF;
+
+// Decode the code point starting at s[0]; s must not be empty. A well-formed
UTF-8 sequence
+// yields its code point and its byte length; any ill-formed byte (an illegal
lead byte, a
+// truncated sequence or a bad continuation byte) yields the fake code point
0x110000+byte (still
+// < 2^21, so it cannot collide with a legal one) and consumes exactly one
byte.
+//
+// *consumed is what keeps a caller's cursor in sync with the decoder.
Advancing by the length
+// guessed from the lead byte instead would swallow the bytes following an
ill-formed sequence --
+// regex metacharacters among them -- and silently compile a different pattern
than the engine
+// sees.
+uint32_t decode_one_cp(std::string_view s, size_t* consumed) {
+ const auto c = static_cast<unsigned char>(s[0]);
+ const int l = utf8_len(c);
+ *consumed = 1;
+ if (l == 1) {
+ return c < 0x80 ? c : 0x110000U + c;
+ }
+ if (static_cast<size_t>(l) > s.size()) {
+ return 0x110000U + c;
+ }
+ uint32_t v = 0;
+ if (l == 2) {
+ v = c & 0x1FU;
+ } else if (l == 3) {
+ v = c & 0x0FU;
+ } else {
+ v = c & 0x07U;
+ }
+ for (int k = 1; k < l; k++) {
+ const auto cc = static_cast<unsigned char>(s[k]);
+ if ((cc & 0xC0) != 0x80) {
+ return 0x110000U + c;
+ }
+ v = (v << 6) | (cc & 0x3FU);
+ }
+ // A sequence can be well-formed byte by byte and still be ill-formed as
UTF-8. Decoding one
+ // to the code point it spells would be worse than dropping it, because
the compiler would
+ // then demand grams of that code point's canonical encoding -- bytes the
row never held. The
+ // extractor treats these bytes as a separator and stores no gram across
them, so a row
+ // holding `C0 AF` stores nothing for `/`, while `C0 AF` decoded as U+002F
asks for `/`
+ // grams and would filter that row away. Three shapes are rejected here:
+ // - overlong: fewer bits set than the length promises (`C0 AF` for
U+002F);
+ // - surrogate halves U+D800..U+DFFF, which UTF-8 may not encode;
+ // - anything above U+10FFFF.
+ static constexpr uint32_t kOverlongFloor[5] = {0, 0, 0x80, 0x800, 0x10000};
+ if (v < kOverlongFloor[l] || (v >= 0xD800U && v <= 0xDFFFU) || v >
kMaxCodePoint) {
+ return 0x110000U + c;
+ }
+ *consumed = static_cast<size_t>(l);
+ return v;
+}
+
+// Encode one code point as UTF-8 and append it to out.
+void encode_cp(uint32_t cp, std::string* out) {
+ if (cp < 0x80) {
+ out->push_back((char)cp);
+ } else if (cp < 0x800) {
+ out->push_back((char)(0xC0 | (cp >> 6)));
+ out->push_back((char)(0x80 | (cp & 0x3F)));
+ } else if (cp < 0x10000) {
+ out->push_back((char)(0xE0 | (cp >> 12)));
+ out->push_back((char)(0x80 | ((cp >> 6) & 0x3F)));
+ out->push_back((char)(0x80 | (cp & 0x3F)));
+ } else {
+ out->push_back((char)(0xF0 | (cp >> 18)));
+ out->push_back((char)(0x80 | ((cp >> 12) & 0x3F)));
+ out->push_back((char)(0x80 | ((cp >> 6) & 0x3F)));
+ out->push_back((char)(0x80 | (cp & 0x3F)));
+ }
+}
+
+using NP = std::unique_ptr<RegexNode>;
+
+NP mk(RegexNode::Type t) {
+ auto p = std::make_unique<RegexNode>();
+ p->type = t;
+ return p;
+}
+
+// ASCII K and S also match the Kelvin sign and long s under the scalar
engines' Unicode
+// case-insensitive matching. Keep the same expansion for literals and small
character classes.
+void append_ascii_case_variants(uint32_t cp, std::vector<std::string>* items) {
+ items->emplace_back(1, static_cast<char>(cp));
+ const uint32_t lower = cp >= 'A' && cp <= 'Z' ? cp + ('a' - 'A') : cp;
+ if (lower < 'a' || lower > 'z') {
+ return;
+ }
+ items->emplace_back(1, static_cast<char>(cp == lower ? cp - ('a' - 'A') :
lower));
+ if (lower == 'k') {
+ items->emplace_back("K");
+ } else if (lower == 's') {
+ items->emplace_back("ſ");
+ }
+}
+
+// Recursive-descent parser for the supported regex subset.
+struct Parser {
+ std::string_view p;
+ size_t i = 0;
+ bool icase = false;
+ bool ok = true;
+ std::string err;
+ int depth = 0; // current group nesting depth, see kMaxNestingDepth
+
+ explicit Parser(std::string_view s) : p(s) {}
+
+ bool eof() const { return i >= p.size(); }
+ char peek() const { return eof() ? 0 : p[i]; }
+
+ uint32_t next_cp(std::string* utf8) {
+ if (eof()) {
+ // Defensive fallback: every normal call site checks that a
character is still
+ // available before entering next_cp; this merely distrusts the
caller and avoids an
+ // out-of-bounds p[i] read at i==size() on a string_view, which --
unlike the
+ // std::string the prototype used -- is not guaranteed to be
NUL-terminated.
+ utf8->clear();
+ return 0;
+ }
+ // Advance by however many bytes the decoder actually consumed, never
by the length
+ // guessed from the lead byte: an ill-formed sequence consumes exactly
one byte, and
+ // advancing further would swallow the bytes that follow it --
including a regex
+ // metacharacter that may sit there -- and compile a pattern the
engine never saw.
+ size_t consumed = 0;
+ const uint32_t cp = decode_one_cp(p.substr(i), &consumed);
+ *utf8 = std::string(p.substr(i, consumed));
+ i += consumed;
+ return cp;
+ }
+
+ NP parse() {
+ NP r = parse_alt();
+ if (!eof()) {
+ ok = false;
+ err = "trailing input at " + std::to_string(i);
+ }
+ return r;
+ }
+
+ NP parse_alt() {
+ std::vector<NP> branches;
+ branches.push_back(parse_cat());
+ while (peek() == '|') {
+ i++;
+ branches.push_back(parse_cat());
+ }
+ if (branches.size() == 1) {
+ return std::move(branches[0]);
+ }
+ NP a = mk(RegexNode::Type::ALT);
+ a->kids = std::move(branches);
+ return a;
+ }
+
+ NP parse_cat() {
+ NP c = mk(RegexNode::Type::CAT);
+ while (!eof() && peek() != '|' && peek() != ')') {
+ if (peek() == '\\' && i + 1 < p.size() && p[i + 1] == 'Q') {
+ append_quoted_literals(&c->kids);
+ if (!c->kids.empty()) {
+ // A quote adds individual literal atoms. If it is empty,
a following
+ // quantifier still applies to the preceding atom,
including a group or
+ // repeat. Keep this token boundary: '+\\Q\\E?' must not
become lazy '+?'.
+ c->kids.back() = parse_quant(std::move(c->kids.back()));
+ }
+ continue;
+ }
+ NP atom = parse_atom();
+ if (!ok) {
+ return c;
+ }
+ if (!atom) {
+ continue; // e.g. a flags-only empty atom such as (?i)
+ }
+ atom = parse_quant(std::move(atom));
+ c->kids.push_back(std::move(atom));
+ }
+ return c;
+ }
+
+ void append_quoted_literals(std::vector<NP>* atoms) {
+ i += 2; // '\\Q'
+ while (!eof() && !(peek() == '\\' && i + 1 < p.size() && p[i + 1] ==
'E')) {
+ std::string utf8;
+ atoms->push_back(make_lit(next_cp(&utf8)));
+ }
+ if (!eof()) {
+ i += 2; // '\\E'
+ }
+ }
+
+ NP parse_quant(NP a) {
+ while (!eof()) {
+ char c = peek();
+ if (c == '*') {
+ i++;
+ NP s = mk(RegexNode::Type::STAR);
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else if (c == '+') {
+ i++;
+ NP s = mk(RegexNode::Type::PLUS);
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else if (c == '?') {
+ i++;
+ NP s = mk(RegexNode::Type::QUEST);
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else if (c == '{') {
+ size_t save = i;
+ i++;
+ int mn = 0;
+ int mx = -1;
+ bool has = false;
+ while (!eof() && std::isdigit(static_cast<unsigned
char>(peek()))) {
+ mn = mn * 10 + (peek() - '0');
+ i++;
+ has = true;
+ }
+ if (!has) {
+ i = save;
+ break;
+ }
+ if (peek() == ',') {
+ i++;
+ if (std::isdigit(static_cast<unsigned char>(peek()))) {
+ mx = 0;
+ while (!eof() && std::isdigit(static_cast<unsigned
char>(peek()))) {
+ mx = mx * 10 + (peek() - '0');
+ i++;
+ }
+ }
+ } else {
+ mx = mn;
+ }
+ if (peek() != '}') {
+ i = save;
+ break;
+ }
+ i++;
+ NP s = mk(RegexNode::Type::REPEAT);
+ s->rmin = mn;
+ s->rmax = mx;
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else {
+ break;
+ }
+ if (peek() == '?') {
+ i++; // a lazy quantifier does not change the match set
+ }
+ }
+ return a;
+ }
+
+ // Hex value of a `\x` escape in class_escape: on entry "\x" has already
been consumed (i
+ // points at the brace or at the first hex digit). Ruling R12: the
`\x{...}` form requires at
+ // least one hex digit inside the braces and the braces must be closed;
the bare `\xHH` form
+ // requires exactly two hex digits, and anything shorter (end of string,
or a non-hex
+ // character) is an error, matching RE2's rejection of `\x4`. On success
the value is written
+ // to *v and true is returned; on failure ok=false and err are set and
false is returned (the
+ // caller then returns immediately). Split out of class_escape to reduce
its
+ // complexity/length; the semantics are identical to the original inline
code.
+ bool parse_hex_escape_value(uint32_t* v) {
+ *v = 0;
+ if (peek() == '{') {
+ i++;
+ int cnt = 0;
+ while (!eof() && peek() != '}') {
+ if (!std::isxdigit(static_cast<unsigned char>(peek()))) {
+ ok = false;
+ err = "bad \\x escape";
+ return false;
+ }
+ *v = *v * 16 +
+ (std::isdigit(static_cast<unsigned char>(peek()))
+ ? peek() - '0'
+ : (std::tolower(static_cast<unsigned
char>(peek())) - 'a' + 10));
+ i++;
+ cnt++;
+ }
+ if (eof() || cnt == 0) {
+ ok = false;
+ err = "bad \\x escape";
+ return false;
+ }
+ i++; // consume '}'
+ return true;
+ }
+ for (int cnt = 0; cnt < 2; cnt++) {
+ if (eof() || !std::isxdigit(static_cast<unsigned char>(peek()))) {
+ ok = false;
+ err = "bad \\x escape";
+ return false;
+ }
+ *v = *v * 16 +
+ (std::isdigit(static_cast<unsigned char>(peek()))
+ ? peek() - '0'
+ : (std::tolower(static_cast<unsigned char>(peek()))
- 'a' + 10));
+ i++;
+ }
+ return true;
+ }
+
+ // Decode only character escapes whose meaning is shared by the scalar
engines. Other
+ // letter/digit escapes may denote assertions, classes or backreferences;
treating them as
+ // literals could exclude matching rows. Three-digit octal avoids short
numeric escapes'
+ // ambiguity with backreferences.
+ bool parse_character_escape(uint32_t* cp) {
+ const char c = p[i++];
+ switch (c) {
+ case 'a':
+ *cp = '\a';
+ return true;
+ case 'f':
+ *cp = '\f';
+ return true;
+ case 'n':
+ *cp = '\n';
+ return true;
+ case 'r':
+ *cp = '\r';
+ return true;
+ case 't':
+ *cp = '\t';
+ return true;
+ case 'x':
+ return parse_hex_escape_value(cp);
+ default:
+ if (c >= '0' && c <= '7' && i + 1 < p.size() && p[i] >= '0' &&
p[i] <= '7' &&
Review Comment:
[P1] Do not compile Boost octal syntax with this three-digit rule. The
scalar Boost fallback reads `\0141` as octal `a` (the new Boost recall matrix
explicitly pins that), while this parser consumes `\014` as form-feed and
leaves literal `1`. A pattern forced onto Boost by an invalid UTF-8 byte can
still compile past that byte and require the resulting form-feed/`1` grams,
excluding a row that Boost matches before scalar recheck. The existing Boost
case starts with lookahead, so gram compilation becomes ALL before reaching
this escape and cannot catch the mismatch. Please conservatively degrade
Boost-ambiguous octal/escaped forms and add a real Boost-path recall case whose
gram query is otherwise selective.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
