Line data Source code
1 : /**
2 : Copyright (c) 2020-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #include "SPSearchConfiguration.h"
25 : #include "SPHtmlParser.h"
26 : #include "SPValid.h"
27 : #include <inttypes.h>
28 :
29 : namespace STAPPLER_VERSIONIZED stappler::search {
30 :
31 : static StemmerEnv *Configuration_makeLocalConfig(StemmerEnv *orig);
32 : static void Stemmer_Reader_run(StringView origin, Function<void(const StringView &, const Callback<void()> &cancelCb)> &&cb);
33 : static void *StemmerEnv_getUserData(StemmerEnv *);
34 :
35 208425 : static bool stemWordDefault(Language lang, StemmerEnv *env, ParserToken tok, StringView word, const Callback<void(StringView)> &cb, const StringView *stopwords) {
36 208425 : switch (tok) {
37 93600 : case ParserToken::AsciiWord:
38 : case ParserToken::AsciiHyphenatedWord:
39 : case ParserToken::HyphenatedWord_AsciiPart:
40 : case ParserToken::Word:
41 : case ParserToken::HyphenatedWord:
42 : case ParserToken::HyphenatedWord_Part:
43 : switch (lang) {
44 11700 : case Language::Simple: {
45 11700 : auto str = normalizeWord(word);
46 11700 : if (stopwords && isStopword(str, stopwords)) {
47 0 : return false;
48 : }
49 11700 : cb(str);
50 11700 : break;
51 11700 : }
52 81900 : default: {
53 81900 : auto str = normalizeWord(word);
54 81900 : if (stopwords && isStopword(str, stopwords)) {
55 0 : return false;
56 : }
57 81900 : return stemWord(str, cb, env);
58 : break;
59 81900 : }
60 : }
61 11700 : break;
62 :
63 14725 : case ParserToken::NumWord:
64 : case ParserToken::NumHyphenatedWord:
65 : case ParserToken::HyphenatedWord_NumPart: {
66 14725 : auto str = normalizeWord(word);
67 14725 : if (stopwords && isStopword(str, stopwords)) {
68 0 : return false;
69 : }
70 14725 : cb(str);
71 14725 : break;
72 14725 : }
73 :
74 25 : case ParserToken::Email: {
75 25 : auto str = normalizeWord(word);
76 25 : valid::validateEmail(str);
77 25 : if (stopwords && isStopword(str, stopwords)) {
78 0 : return false;
79 : }
80 25 : cb(str);
81 25 : break;
82 25 : }
83 :
84 575 : case ParserToken::Url: {
85 575 : auto str = normalizeWord(word);
86 575 : valid::validateUrl(str);
87 575 : if (stopwords && isStopword(str, stopwords)) {
88 0 : return false;
89 : }
90 575 : cb(str);
91 575 : break;
92 575 : }
93 :
94 900 : case ParserToken::Version:
95 : case ParserToken::Path:
96 : case ParserToken::ScientificFloat: {
97 900 : auto str = normalizeWord(word);
98 900 : if (stopwords && isStopword(str, stopwords)) {
99 0 : return false;
100 : }
101 900 : cb(str);
102 900 : break;
103 900 : }
104 :
105 8050 : case ParserToken::Float:
106 : case ParserToken::Integer: {
107 8050 : cb(word);
108 8050 : break;
109 : }
110 :
111 500 : case ParserToken::Custom: {
112 500 : StringViewUtf8 tmp(word);
113 500 : auto num = tmp.readChars<StringViewUtf8::CharGroup<CharGroupId::Numbers>>();
114 500 : if (num.size() == 2) {
115 500 : if (tmp.is(':') || tmp.is('-') || tmp.is(u'–')) {
116 500 : bool cond = tmp.is('-') || tmp.is(u'–');
117 500 : String str; str.reserve(word.size());
118 500 : if (cond) {
119 400 : StringViewUtf8 word2(word);
120 1600 : while (!word2.empty()) {
121 1200 : auto r = word2.readUntil<StringViewUtf8::CharGroup<CharGroupId::WhiteSpace>, StringViewUtf8::Chars<u'–'>, StringViewUtf8::Chars<':'>>();
122 1200 : if (!r.empty()) {
123 1200 : str.append(r.data(), r.size());
124 : }
125 1200 : if (word2.is(u'–')) {
126 200 : str.emplace_back('-');
127 200 : ++ word2;
128 1000 : } else if (word2.is(':')) {
129 600 : str.emplace_back(':');
130 600 : ++ word2;
131 : } else {
132 400 : auto space = word2.readChars<StringViewUtf8::CharGroup<CharGroupId::WhiteSpace>>();
133 400 : if (cond && !space.empty() && !r.empty()) {
134 0 : str.emplace_back('/');
135 : }
136 : }
137 : }
138 : } else {
139 200 : while (!word.empty()) {
140 100 : auto r = word.readUntil<StringViewUtf8::CharGroup<CharGroupId::WhiteSpace>>();
141 100 : if (!r.empty()) {
142 100 : str.append(r.data(), r.size());
143 : }
144 : }
145 : }
146 500 : cb(string::tolower<Interface>(StringView(str)));
147 500 : return true;
148 500 : }
149 : }
150 0 : auto str = normalizeWord(word);
151 0 : if (stopwords && isStopword(str, stopwords)) {
152 0 : return false;
153 : }
154 0 : cb(str);
155 0 : break;
156 0 : }
157 90000 : case ParserToken::XMLEntity:
158 : case ParserToken::Blank:
159 90000 : return false;
160 : break;
161 : }
162 36025 : return true;
163 : }
164 :
165 : struct Configuration::Data : AllocBase {
166 : pool_t *pool = nullptr;
167 : std::atomic<uint32_t> refCount = 1;
168 : Language language = Language::Simple;
169 : StemmerEnv *primary = nullptr;
170 : StemmerEnv *secondary = nullptr;
171 :
172 : Map<ParserToken, StemmerCallback> stemmers;
173 :
174 : PreStemCallback preStem;
175 : const StringView *customStopwords = nullptr;
176 :
177 225 : Data(pool_t *p, Language lang)
178 225 : : pool(p), language(lang), primary(search::getStemmer(language))
179 450 : , secondary(search::getStemmer((lang == Language::Simple) ? Language::Simple : Language::English)) { }
180 : };
181 :
182 25 : Configuration::Configuration() : Configuration(Language::English) { }
183 :
184 225 : Configuration::Configuration(Language lang) {
185 225 : pool::initialize();
186 225 : auto p = pool::create(pool::acquire());
187 225 : perform([&, this] {
188 225 : data = new (p) Data(p, lang);
189 225 : }, p);
190 225 : }
191 :
192 200 : Configuration::~Configuration() {
193 400 : if (data->refCount.fetch_sub(1) == 1) {
194 200 : data->~Data();
195 200 : pool::destroy(data->pool);
196 200 : pool::terminate();
197 : }
198 200 : }
199 :
200 50 : void Configuration::setLanguage(Language lang) {
201 225 : perform([&, this] {
202 50 : auto prev = data->language;
203 50 : auto prevSec = (prev == Language::Simple) ? Language::Simple : Language::English;
204 50 : auto newSec = (lang == Language::Simple) ? Language::Simple : Language::English;
205 50 : data->language = lang;
206 50 : data->primary = search::getStemmer(data->language);
207 50 : if (prevSec != newSec) {
208 25 : data->secondary = search::getStemmer(newSec);
209 : }
210 50 : }, data->pool);
211 50 : }
212 :
213 25 : Language Configuration::getLanguage() const {
214 25 : return data->language;
215 : }
216 :
217 125 : void Configuration::setStemmer(ParserToken tok, StemmerCallback &&cb) {
218 375 : perform([&, this] {
219 125 : data->stemmers.emplace(tok, move(cb));
220 125 : }, data->pool);
221 125 : }
222 :
223 75 : Configuration::StemmerCallback Configuration::getStemmer(ParserToken tok) const {
224 75 : auto it = data->stemmers.find(tok);
225 75 : if (it != data->stemmers.end()) {
226 25 : return it->second;
227 : }
228 :
229 150 : return StemmerCallback([&, lang = data->language, env = getEnvForToken(tok), stopwords = data->customStopwords]
230 50 : (StringView word, const Callback<void(StringView)> &cb) -> bool {
231 50 : return stemWordDefault(lang, env, tok, word, cb, stopwords);
232 50 : });
233 : }
234 :
235 25 : void Configuration::setCustomStopwords(const StringView *w) {
236 25 : data->customStopwords = w;
237 25 : }
238 :
239 25 : const StringView *Configuration::getCustomStopwords() const {
240 25 : return data->customStopwords;
241 : }
242 :
243 25 : void Configuration::setPreStem(PreStemCallback &&cb) {
244 100 : perform([&, this] {
245 25 : data->preStem = move(cb);
246 25 : }, data->pool);
247 :
248 25 : }
249 25 : const Configuration::PreStemCallback &Configuration::getPreStem() const {
250 25 : return data->preStem;
251 : }
252 :
253 550 : void Configuration::stemPhrase(const StringView &str, const StemWordCallback &cb) const {
254 550 : parsePhrase(str, [&, this] (StringView word, ParserToken tok) {
255 99425 : if (data->preStem != nullptr && !isWordPart(tok)) {
256 39575 : auto ret = data->preStem(word, tok);
257 39575 : if (!ret.empty()) {
258 1250 : for (auto &it : ret) {
259 750 : auto str = normalizeWord(it);
260 750 : cb(word, str, tok);
261 750 : }
262 500 : return isComplexWord(tok) ? ParserStatus::PreventSubdivide : ParserStatus::Continue;
263 : }
264 39575 : }
265 98925 : stemWord(word, tok, cb);
266 98925 : return ParserStatus::Continue;
267 : });
268 550 : }
269 :
270 10100 : size_t Configuration::makeSearchVector(SearchVector &vec, StringView str, SearchData::Rank rank, size_t counter,
271 : const Callback<void(StringView, StringView, ParserToken)> &cb) const {
272 10100 : if (str.empty()) {
273 50 : return counter;
274 : }
275 :
276 41975 : auto pushWord = [&] (StringView s) -> const StringView * {
277 121600 : ++ vec.documentLength;
278 41975 : auto it = vec.words.find(s);
279 41975 : if (it == vec.words.end()) {
280 18825 : return &vec.words.emplace(s.pdup(vec.words.get_allocator()), SearchVector::MatchVector({pair(counter, rank)})).first->first;
281 : } else {
282 23150 : auto value = pair(counter, rank);
283 23150 : auto iit = std::lower_bound(it->second.begin(), it->second.end(), value,
284 40900 : [&] (const Pair<size_t, SearchData::Rank> &l, const Pair<size_t, SearchData::Rank> &r) {
285 40900 : if (l.first != r.first) {
286 40900 : return l.first < r.first;
287 : } else {
288 0 : return toInt(l.second) < toInt(r.second);
289 : }
290 23150 : });
291 23150 : if (iit == it->second.end()) {
292 23150 : it->second.emplace_back(value);
293 0 : } else if (*iit != value) {
294 0 : it->second.emplace(iit, value);
295 : }
296 23150 : return &it->first;
297 : }
298 10050 : };
299 :
300 10050 : parsePhrase(str, [&, this] (StringView word, ParserToken tok) {
301 83850 : if (tok != ParserToken::Blank && !isWordPart(tok)) {
302 45125 : ++ counter;
303 : }
304 :
305 83850 : if (data->preStem != nullptr && !isWordPart(tok)) {
306 29300 : auto ret = data->preStem(word, tok);
307 29300 : if (ret.size() == 1) {
308 375 : auto str = normalizeWord(ret.back());
309 375 : if (auto sPtr = pushWord(str)) {
310 375 : if (cb != nullptr) { cb(*sPtr, word, tok); }
311 375 : return isComplexWord(tok) ? ParserStatus::PreventSubdivide : ParserStatus::Continue;
312 : }
313 29300 : } else if (!ret.empty()) {
314 500 : for (auto &it : ret) {
315 375 : auto str = normalizeWord(it);
316 375 : pushWord(str);
317 375 : }
318 125 : return isComplexWord(tok) ? ParserStatus::PreventSubdivide : ParserStatus::Continue;
319 : }
320 29300 : }
321 :
322 83350 : stemWord(word, tok, [&] (StringView w, StringView s, ParserToken tok) {
323 41225 : if (!s.empty()) {
324 41225 : if (auto sPtr = pushWord(s)) {
325 41225 : if (cb != nullptr) { cb(*sPtr, word, tok); }
326 : }
327 : }
328 41225 : });
329 83350 : return ParserStatus::Continue;
330 : });
331 :
332 10050 : return counter;
333 : }
334 :
335 775 : String Configuration::encodeSearchVectorPostgres(const SearchVector &vec, SearchData::Rank rank) const {
336 775 : StringStream ret;
337 6200 : for (auto &it : vec.words) {
338 5425 : if (!ret.empty()) {
339 4650 : ret << " ";
340 : }
341 :
342 5425 : StringView r(it.first);
343 5425 : ret << "'";
344 10850 : while (!r.empty()) {
345 5425 : auto v = r.readUntil<StringView::Chars<'\''>>();
346 5425 : if (!v.empty()) {
347 5425 : ret << v;
348 : }
349 5425 : if (r.is('\'')) {
350 25 : ret << "''";
351 25 : ++ r;
352 : }
353 : }
354 5425 : ret << "':";
355 23175 : for (auto &v : it.second) {
356 17750 : if (ret.weak().back() != ':') { ret << ","; }
357 17750 : ret << v.first;
358 17750 : auto r = v.second;
359 17750 : if (r == SearchRank::Unknown) {
360 0 : r = rank;
361 : }
362 17750 : switch (r) {
363 14750 : case SearchRank::A: ret << 'A'; break;
364 3000 : case SearchRank::B: ret << 'B'; break;
365 0 : case SearchRank::C: ret << 'C'; break;
366 0 : case SearchRank::D:
367 : case SearchRank::Unknown:
368 0 : break;
369 : }
370 : }
371 : }
372 1550 : return ret.str();
373 775 : }
374 :
375 1825 : Bytes Configuration::encodeSearchVectorData(const SearchVector &data, SearchData::Rank rank) const {
376 1825 : data::cbor::Encoder<Interface> enc(true);
377 1825 : data::cbor::_writeArrayStart(enc, 3);
378 1825 : data::cbor::_writeInt(enc, 1); // version
379 1825 : data::cbor::_writeInt(enc, data.documentLength); // version
380 1825 : data::cbor::_writeMapStart(enc, data.words.size());
381 14925 : for (auto &it : data.words) {
382 13100 : enc.write(it.first);
383 13100 : _writeArrayStart(enc, it.second.size() * 2);
384 36875 : for (auto &iit : it.second) {
385 23775 : data::cbor::_writeInt(enc, iit.first);
386 23775 : data::cbor::_writeInt(enc, toInt( (iit.second == SearchData::Rank::Unknown) ? rank : iit.second ));
387 : }
388 : }
389 1825 : auto result = enc.data();
390 1825 : auto r = data::compress<Interface>(result.data(), result.size(), EncodeFormat::Compression::LZ4HCCompression, true);
391 1825 : if (r.empty()) {
392 1775 : return result;
393 : }
394 50 : return r;
395 1825 : }
396 :
397 25 : void Configuration::stemHtml(const StringView &str, const StemWordCallback &cb) const {
398 25 : parseHtml(str, [&, this] (StringView str) {
399 175 : stemPhrase(str, cb);
400 175 : });
401 25 : }
402 :
403 208425 : bool Configuration::stemWord(const StringView &word, ParserToken tok, const StemWordCallback &cb) const {
404 208425 : auto it = data->stemmers.find(tok);
405 208425 : if (it != data->stemmers.end()) {
406 100 : return it->second(word, [&] (StringView stem) {
407 50 : cb(word, stem, tok);
408 50 : });
409 : } else {
410 416750 : return stemWordDefault(data->language, getEnvForToken(tok), tok, word, [&] (StringView stem) {
411 110625 : cb(word, stem, tok);
412 416750 : }, data->customStopwords);
413 : }
414 : }
415 :
416 208425 : StemmerEnv *Configuration::getEnvForToken(ParserToken tok) const {
417 208425 : switch (tok) {
418 58250 : case ParserToken::AsciiWord:
419 : case ParserToken::AsciiHyphenatedWord:
420 : case ParserToken::HyphenatedWord_AsciiPart:
421 58250 : if (data->secondary) {
422 47100 : if (memory::pool::acquire() == StemmerEnv_getUserData(data->secondary)) {
423 0 : return data->secondary;
424 : } else {
425 47100 : return Configuration_makeLocalConfig(data->secondary);
426 : }
427 : }
428 11150 : break;
429 35375 : case ParserToken::Word:
430 : case ParserToken::HyphenatedWord:
431 : case ParserToken::HyphenatedWord_Part:
432 35375 : if (data->primary) {
433 34825 : if (memory::pool::acquire() == StemmerEnv_getUserData(data->primary)) {
434 0 : return data->primary;
435 : } else {
436 34825 : return Configuration_makeLocalConfig(data->primary);
437 : }
438 : }
439 550 : break;
440 :
441 114800 : case ParserToken::NumWord:
442 : case ParserToken::NumHyphenatedWord:
443 : case ParserToken::HyphenatedWord_NumPart:
444 : case ParserToken::Email:
445 : case ParserToken::Url:
446 : case ParserToken::Version:
447 : case ParserToken::Path:
448 : case ParserToken::Integer:
449 : case ParserToken::Float:
450 : case ParserToken::ScientificFloat:
451 : case ParserToken::XMLEntity:
452 : case ParserToken::Custom:
453 : case ParserToken::Blank:
454 114800 : return nullptr;
455 : }
456 11700 : return nullptr;
457 : }
458 :
459 100 : String Configuration::makeHeadline(const HeadlineConfig &cfg, const StringView &origin, const Vector<String> &stemList) const {
460 100 : memory::PoolInterface::StringStreamType result;
461 100 : result.reserve(origin.size() + (cfg.startToken.size() + cfg.stopToken.size()) * stemList.size());
462 :
463 100 : bool isOpen = false;
464 100 : StringViewUtf8 r(origin);
465 100 : StringView dropSep;
466 :
467 100 : parsePhrase(origin, [&, this] (StringView word, ParserToken tok) {
468 900 : auto status = ParserStatus::Continue;
469 1400 : if (tok == ParserToken::Blank || !stemWord(word, tok, [&, this] (StringView word, StringView stem, ParserToken tok) {
470 500 : auto it = std::lower_bound(stemList.begin(), stemList.end(), stem);
471 500 : if (it != stemList.end() && *it == stem) {
472 100 : if (!isOpen) {
473 100 : result << cfg.startToken;
474 100 : isOpen = true;
475 500 : } else if (!dropSep.empty()) {
476 0 : result << dropSep;
477 0 : dropSep.clear();
478 : }
479 100 : if (isComplexWord(tok)) {
480 0 : status = ParserStatus::PreventSubdivide;
481 : }
482 : } else {
483 400 : if (isOpen) {
484 100 : result << cfg.stopToken;
485 100 : isOpen = false;
486 100 : if (!dropSep.empty()) {
487 100 : result << dropSep;
488 100 : dropSep.clear();
489 : }
490 : }
491 400 : if (isComplexWord(tok)) {
492 0 : return;
493 : }
494 : }
495 500 : result << word;
496 : })) {
497 400 : if (isOpen) {
498 100 : if (!dropSep.empty()) {
499 0 : dropSep = StringView(dropSep.data(), word.data() + word.size() - dropSep.data());
500 : } else {
501 100 : dropSep = word;
502 : }
503 : } else {
504 300 : result << word;
505 : }
506 : }
507 900 : return status;
508 : });
509 :
510 100 : if (isOpen) {
511 0 : result << cfg.stopToken;
512 0 : isOpen = false;
513 : }
514 :
515 200 : return result.str();
516 100 : }
517 :
518 225 : String Configuration::makeHtmlHeadlines(const HeadlineConfig &cfg, const StringView &origin, const Vector<String> &stemList, size_t count) const {
519 225 : return makeHeadlines(cfg, [&] (const Function<bool(const StringView &, const StringView &)> &cb) {
520 225 : Stemmer_Reader_run(origin, [&] (const StringView &str, const Callback<void()> &cancelCb) {
521 1300 : if (!cb(str, StringView())) {
522 50 : cancelCb();
523 : }
524 1300 : });
525 450 : }, stemList, count);
526 : }
527 :
528 225 : String Configuration::makeHeadlines(const HeadlineConfig &cfg, const Callback<void(const Function<bool(const StringView &frag, const StringView &tag)>)> &cb,
529 : const Vector<String> &stemList, size_t count) const {
530 :
531 : using SplitTokens = StringViewUtf8::MatchCompose<
532 : StringViewUtf8::MatchCharGroup<CharGroupId::WhiteSpace>,
533 : StringViewUtf8::MatchChars<'-', u'—', u'\'', u'«', u'»', u'’', u'“', '(', ')', '"', ',', '*', ':', ';', '/', '\\'>>;
534 :
535 : using TrimToken = StringView::Chars<'.'>;
536 :
537 : struct WordIndex {
538 : StringView word;
539 : uint16_t index;
540 : uint16_t selectedCount; // selected words in block
541 : uint16_t allWordsCount; // all words in block;
542 : const WordIndex *end;
543 : };
544 :
545 225 : WordIndex *topIndex = nullptr;
546 225 : StringStream ret; ret.reserve(1_KiB);
547 :
548 625 : auto rateWord = [&] (WordIndex &index, WordIndex *list, size_t listCount) {
549 625 : index.end = &index;
550 625 : index.selectedCount = 1;
551 625 : index.allWordsCount = 1;
552 950 : while (listCount > 0) {
553 350 : uint16_t offset = list->index - index.index;
554 350 : if (offset < cfg.maxWords) {
555 325 : ++ index.selectedCount;
556 325 : index.allWordsCount = offset;
557 325 : index.end = list;
558 : } else {
559 25 : break;
560 : }
561 :
562 325 : ++ list;
563 325 : -- listCount;
564 : }
565 :
566 625 : if (!topIndex || index.selectedCount > topIndex->selectedCount
567 275 : || (index.selectedCount == topIndex->selectedCount && index.allWordsCount < topIndex->allWordsCount)) {
568 350 : topIndex = &index;
569 : }
570 850 : };
571 :
572 350 : auto writeFragmentWords = [&] (StringStream &out, const StringView &str, const std::array<WordIndex, 32> &words, const WordIndex *word) {
573 350 : bool isOpen = false;
574 600 : for (auto it = word; it < word->end; ++ it) {
575 250 : if (!isOpen) {
576 225 : out << cfg.startToken;
577 : }
578 250 : out << it->word;
579 250 : auto next = it + 1;
580 250 : if (next <= word->end && it->index + 1 == next->index) {
581 150 : isOpen = true;
582 : } else {
583 100 : isOpen = false;
584 100 : out << cfg.stopToken;
585 : }
586 :
587 250 : if (next <= word->end) {
588 250 : out << StringView(it->word.data() + it->word.size(), next->word.data() - (it->word.data() + it->word.size()));
589 : }
590 : }
591 :
592 350 : if (!isOpen) {
593 225 : out << cfg.startToken;
594 : }
595 350 : out << word->end->word;
596 350 : out << cfg.stopToken;
597 350 : isOpen = false;
598 350 : };
599 :
600 125 : auto makeFragmentPrefix = [&] (StringStream &out, const StringView &str, size_t numWords, size_t allWords) {
601 125 : if (numWords == allWords) {
602 0 : out << str;
603 0 : return;
604 125 : } else if (numWords == 0) {
605 0 : return;
606 : }
607 :
608 125 : StringViewUtf8 r(str);
609 800 : while (!r.empty() && numWords > 0) {
610 675 : r.backwardSkipChars<SplitTokens>();
611 675 : auto tmp = StringViewUtf8(r.backwardReadUntil<SplitTokens>());
612 :
613 675 : auto tmpR = tmp;
614 675 : tmpR.trimChars<TrimToken>();
615 :
616 675 : if (string::getUtf16Length(tmpR) > cfg.shortWord) {
617 500 : -- numWords;
618 : }
619 : }
620 :
621 125 : if (!r.empty()) {
622 125 : out << cfg.separator << " ";
623 : }
624 :
625 125 : out << StringView(r.data() + r.size(), (str.data() + str.size()) - (r.data() + r.size()));
626 225 : };
627 :
628 175 : auto makeFragmentSuffix = [&] (StringStream &out, const StringView &str, size_t numWords, size_t allWords) {
629 175 : if (numWords == allWords) {
630 0 : out << str;
631 0 : return;
632 175 : } else if (numWords == 0) {
633 0 : return;
634 : }
635 :
636 175 : StringViewUtf8 r(str);
637 1250 : while (!r.empty() && numWords > 0) {
638 1075 : auto sep = StringViewUtf8(r.readChars<SplitTokens>());
639 1075 : auto tmp = StringViewUtf8(r.readUntil<SplitTokens>());
640 :
641 1075 : auto tmpR = tmp;
642 1075 : tmpR.trimChars<TrimToken>();
643 :
644 1075 : out << sep << tmp;
645 :
646 1075 : if (string::getUtf16Length(tmpR) > cfg.shortWord) {
647 825 : -- numWords;
648 : }
649 : }
650 :
651 175 : if (!r.empty()) {
652 175 : out << " " << cfg.separator;
653 : }
654 225 : };
655 :
656 350 : auto makeFragment = [&] (StringStream &out, const StringView &str, const StringView &tagId, const std::array<WordIndex, 32> &words, const WordIndex *word, size_t idx) {
657 350 : out << cfg.startFragment;
658 350 : auto prefixView = StringView(str.data(), word->word.data() - str.data());
659 350 : auto suffixView = StringView(word->end->word.data() + word->end->word.size(), str.data() + str.size() - (word->end->word.data() + word->end->word.size()));
660 350 : if (idx < cfg.maxWords) {
661 : // write whole block
662 125 : out << prefixView;
663 125 : writeFragmentWords(out, str, words, word);
664 125 : out << suffixView;
665 225 : } else if (word->allWordsCount < cfg.minWords) {
666 : // make offsets
667 175 : size_t availStart = word->index;
668 175 : size_t availEnd = idx - word->end->index - 1;
669 175 : size_t diff = (cfg.minWords - word->allWordsCount) + 1;
670 :
671 175 : if (availStart >= diff / 2 && availEnd >= diff / 2) {
672 50 : makeFragmentPrefix(out, prefixView, diff / 2, word->index);
673 50 : writeFragmentWords(out, str, words, word);
674 50 : makeFragmentSuffix(out, suffixView, diff / 2, idx - word->end->index - 1);
675 125 : } else if (availStart < diff / 2 && availEnd < diff / 2) {
676 25 : out << prefixView;
677 25 : writeFragmentWords(out, str, words, word);
678 25 : out << suffixView;
679 100 : } else if (availStart < diff / 2) {
680 75 : out << prefixView;
681 75 : writeFragmentWords(out, str, words, word);
682 75 : makeFragmentSuffix(out, suffixView, diff - availStart - 1, idx - word->end->index - 1);
683 25 : } else if (availEnd < diff / 2) {
684 25 : makeFragmentPrefix(out, prefixView, diff - availEnd - 1, word->index);
685 25 : writeFragmentWords(out, str, words, word);
686 25 : out << suffixView;
687 : }
688 : } else {
689 : // try minimal offsets
690 50 : makeFragmentPrefix(out, prefixView, 1, word->index);
691 50 : writeFragmentWords(out, str, words, word);
692 50 : makeFragmentSuffix(out, suffixView, 1, idx - word->end->index - 1);
693 : }
694 350 : out << cfg.stopFragment;
695 :
696 350 : if (cfg.fragmentCallback) {
697 75 : cfg.fragmentCallback(out.weak(), tagId);
698 : }
699 350 : };
700 :
701 225 : cb([&, this] (const StringView &str, const StringView &fragmentTag) -> bool {
702 1300 : std::array<WordIndex, 32> wordsMatch;
703 1300 : uint16_t wordCount = 0;
704 1300 : uint16_t idx = 0;
705 :
706 1300 : bool enabledComplex = false;
707 1300 : parsePhrase(str, [&, this] (StringView word, ParserToken tok) {
708 63300 : auto status = ParserStatus::Continue;
709 63300 : if (tok != ParserToken::Blank && string::getUtf16Length(word) > cfg.shortWord && wordCount < 32) {
710 22475 : if (enabledComplex) {
711 100 : if (isWordPart(tok)) {
712 75 : wordsMatch[wordCount] = WordIndex{word, idx};
713 75 : ++ wordCount;
714 75 : ++ idx;
715 75 : return status;
716 : } else {
717 25 : enabledComplex = false;
718 : }
719 : }
720 22400 : stemWord(word, tok, [&] (StringView word, StringView stem, ParserToken tok) {
721 44625 : auto it = std::lower_bound(stemList.begin(), stemList.end(), stem);
722 20925 : if (it != stemList.end() && string::caseCompare_u(*it, stem) == 0) {
723 575 : if (isComplexWord(tok)) {
724 25 : enabledComplex = true;
725 : } else {
726 550 : wordsMatch[wordCount] = WordIndex{word, idx};
727 550 : ++ wordCount;
728 : }
729 : }
730 20925 : });
731 22400 : ++ idx;
732 : }
733 63225 : return status;
734 : });
735 :
736 1300 : if (wordCount == 0) {
737 950 : return true;
738 : }
739 :
740 975 : for (size_t i = 0; i < wordCount; ++ i) {
741 625 : rateWord(wordsMatch[i], &wordsMatch[i + 1], wordCount - 1 - i);
742 : }
743 :
744 350 : if (topIndex && count > 0) {
745 350 : if (cfg.fragmentCallback) {
746 75 : StringStream out;
747 75 : makeFragment(out, str, fragmentTag, wordsMatch, topIndex, idx);
748 75 : ret << out.weak();
749 75 : } else {
750 275 : makeFragment(ret, str, fragmentTag, wordsMatch, topIndex, idx);
751 275 : -- count;
752 : }
753 : }
754 :
755 350 : if (count == 0) {
756 50 : return false;
757 : }
758 :
759 300 : topIndex = nullptr;
760 300 : return true;
761 : });
762 450 : return ret.str();
763 225 : }
764 :
765 325 : Vector<String> Configuration::stemQuery(const SearchQuery &query) const {
766 325 : Vector<String> queryList;
767 325 : doStemQuery(queryList, query);
768 325 : return queryList;
769 0 : }
770 :
771 800 : void Configuration::doStemQuery(Vector<String> &queryList, const SearchQuery &query) const {
772 800 : if (!query.value.empty()) {
773 475 : emplace_ordered(queryList, query.value);
774 : }
775 1275 : for (auto &it : query.args) {
776 475 : doStemQuery(queryList, it);
777 : }
778 800 : }
779 :
780 : struct Configuration_ParserControl {
781 : Vector<SearchQuery *> stack;
782 : StringView error;
783 : bool neg = false;
784 : bool success = true;
785 : bool strict = false;
786 :
787 3925 : bool popNeg() {
788 3925 : auto tmp = neg;
789 3925 : neg = false;
790 3925 : return tmp;
791 : }
792 :
793 325 : void pushNeg() {
794 325 : neg = !neg;
795 325 : }
796 : };
797 :
798 3100 : static bool Configuration_parseQueryBlank(Configuration_ParserControl &control, StringView r) {
799 275 : auto makeShift = [&] (SearchQuery *q, SearchOp op) {
800 275 : SearchQuery tmp = move(*q);
801 275 : q->clear();
802 275 : q->op = op;
803 275 : q->args.emplace_back(move(tmp));
804 275 : };
805 :
806 7625 : while (!r.empty()) {
807 4600 : auto q = control.stack.back();
808 4600 : r.skipUntil<StringView::Chars<'"', '|', '!', '(', ')'>>();
809 4600 : if (q->block == SearchQuery::Quoted) {
810 : // ignore any punctuation within quotes
811 1100 : if (r[0] != '"') {
812 725 : ++ r;
813 725 : continue;
814 : }
815 : }
816 3875 : switch (r[0]) {
817 775 : case '"':
818 775 : if (q->block != SearchQuery::Quoted) {
819 400 : if (q->op == SearchOp::None) {
820 100 : q->op = SearchOp::Follow;
821 100 : q->block = SearchQuery::Quoted;
822 : } else {
823 300 : if (q->op == SearchOp::Or) {
824 25 : makeShift(q, SearchOp::And);
825 : }
826 300 : auto &top = q->args.emplace_back();
827 300 : top.op = SearchOp::Follow;
828 300 : top.block = SearchQuery::Quoted;
829 300 : top.neg = control.popNeg();
830 300 : control.stack.emplace_back(&top);
831 : }
832 : } else {
833 375 : control.stack.pop_back();
834 : }
835 775 : break;
836 625 : case '|':
837 625 : if (q->op == SearchOp::Or) {
838 100 : auto &top = q->args.emplace_back();
839 100 : control.stack.emplace_back(&top);
840 525 : } else if (q->op == SearchOp::And && q->args.size() <= 1) {
841 325 : q->op = SearchOp::Or;
842 325 : auto &top = q->args.emplace_back();
843 325 : control.stack.emplace_back(&top);
844 200 : } else if (q->op != SearchOp::None || (q->op == SearchOp::None && !q->value.empty()) ) {
845 200 : makeShift(q, SearchOp::Or);
846 200 : auto &top = q->args.emplace_back();
847 200 : control.stack.emplace_back(&top);
848 : }
849 625 : break;
850 325 : case '!': {
851 325 : control.pushNeg();
852 325 : break;
853 : }
854 550 : case '(':
855 550 : if (q->block == SearchQuery::None) {
856 500 : if (q->op == SearchOp::None) {
857 150 : q->op = SearchOp::And;
858 150 : q->block = SearchQuery::Parentesis;
859 : } else {
860 350 : if (q->op == SearchOp::Or) {
861 50 : makeShift(q, SearchOp::And);
862 : }
863 350 : auto &top = q->args.emplace_back();
864 350 : top.op = SearchOp::And;
865 350 : top.block = SearchQuery::Parentesis;
866 350 : top.neg = control.popNeg();
867 350 : control.stack.emplace_back(&top);
868 : }
869 : } else {
870 50 : control.error = StringView("Invalid '(' token within block");
871 50 : if (control.strict) {
872 25 : return false;
873 : }
874 : }
875 525 : break;
876 550 : case ')':
877 550 : if (q->block == SearchQuery::Parentesis) {
878 400 : control.stack.pop_back();
879 : } else {
880 150 : control.error = StringView("Invalid ')' outside of parenthesis");
881 150 : if (control.strict) {
882 50 : return false;
883 : }
884 : }
885 500 : break;
886 1050 : default: break;
887 : }
888 :
889 3800 : ++ r;
890 : }
891 3025 : return true;
892 : }
893 :
894 3325 : static bool Configuration_parseQueryWord(Configuration_ParserControl &control, StringView word, size_t offset = 0, StringView source = StringView()) {
895 3325 : auto q = control.stack.back();
896 :
897 3325 : if (q->op == SearchOp::None) {
898 375 : if (q->value.empty()) {
899 375 : q->value = word.str<memory::PoolInterface>();
900 375 : q->source = source;
901 375 : q->offset = offset;
902 375 : q->neg = control.popNeg();
903 375 : if (control.stack.size() > 1) {
904 375 : control.stack.pop_back();
905 : }
906 : } else {
907 0 : control.error = StringView("Invalid element");
908 0 : if (control.strict) {
909 0 : return false;
910 : }
911 : }
912 2950 : } else if (q->op == SearchOp::And || q->op == SearchOp::Follow) {
913 2900 : auto &v = q->args.emplace_back(SearchQuery(word, offset, source));
914 2900 : v.neg = control.popNeg();
915 2900 : } else {
916 50 : SearchQuery tmp = move(*q);
917 50 : q->clear();
918 50 : q->op = SearchOp::And;
919 50 : q->args.emplace_back(move(tmp));
920 50 : q->args.emplace_back(SearchQuery(word, offset, source));
921 50 : }
922 3325 : return true;
923 : }
924 :
925 1150 : SearchQuery Configuration::parseQuery(StringView str, bool strict, StringView *err) const {
926 1150 : SearchQuery query;
927 1150 : query.op = SearchOp::And;
928 :
929 1150 : Configuration_ParserControl control;
930 1150 : control.stack.emplace_back(&query);
931 1150 : control.strict = strict;
932 :
933 1150 : size_t prev = 0;
934 1150 : size_t counter = 0;
935 1150 : auto ret = search::parsePhrase(str, [&, this] (StringView word, ParserToken tok) {
936 6425 : auto status = isComplexWord(tok) ? ParserStatus::PreventSubdivide : ParserStatus::Continue;
937 6425 : if (tok == ParserToken::Blank) {
938 3100 : if (!Configuration_parseQueryBlank(control, word)) {
939 75 : return ParserStatus::Stop;
940 : }
941 : } else {
942 6650 : ++ counter;
943 3325 : if (data->preStem && !isWordPart(tok)) {
944 200 : auto ret = data->preStem(word, tok);
945 200 : if (!ret.empty()) {
946 3325 : auto offset = counter - prev;
947 75 : prev = counter;
948 300 : for (auto &it : ret) {
949 225 : auto str = normalizeWord(it);
950 225 : if (!Configuration_parseQueryWord(control, str, offset, word)) {
951 0 : return ParserStatus::Stop;
952 : }
953 225 : }
954 75 : return isComplexWord(tok) ? ParserStatus::PreventSubdivide : ParserStatus::Continue;
955 : }
956 200 : }
957 3250 : stemWord(word, tok, [&] (StringView w, StringView s, ParserToken tok) {
958 3100 : if (!s.empty()) {
959 3100 : if (!Configuration_parseQueryWord(control, s, counter - prev, w)) {
960 0 : status = ParserStatus::Stop;
961 : }
962 3100 : prev = counter;
963 : }
964 3100 : });
965 : }
966 6275 : return status;
967 : });
968 :
969 1150 : if (!ret) {
970 75 : if (err) {
971 0 : *err = control.error;
972 : }
973 75 : return SearchQuery();
974 : }
975 :
976 1075 : if (control.stack.back()->block == SearchQuery::Block::Quoted
977 25 : && control.stack.back()->op == SearchOp::Follow
978 1100 : && control.stack.back()->args.empty()) {
979 25 : auto v = control.stack.back();
980 25 : control.stack.pop_back();
981 25 : if (!control.stack.empty()) {
982 25 : if (&control.stack.back()->args.back() == v) {
983 25 : control.stack.back()->args.pop_back();
984 : }
985 : }
986 : }
987 :
988 1075 : query.normalize();
989 1075 : return query;
990 1150 : }
991 :
992 50 : bool Configuration::isMatch(const SearchVector &vec, StringView q) const {
993 50 : auto query = parseQuery(q);
994 100 : return query.isMatch(vec);
995 50 : }
996 :
997 50 : bool Configuration::isMatch(const SearchVector &vec, const SearchQuery &query) const {
998 50 : return query.isMatch(vec);
999 : }
1000 : }
|
