Line data Source code
1 : /**
2 : Copyright (c) 2024 Stappler LLC <admin@stappler.dev>
3 :
4 : Permission is hereby granted, free of charge, to any person obtaining a copy
5 : of this software and associated documentation files (the "Software"), to deal
6 : in the Software without restriction, including without limitation the rights
7 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 : copies of the Software, and to permit persons to whom the Software is
9 : furnished to do so, subject to the following conditions:
10 :
11 : The above copyright notice and this permission notice shall be included in
12 : all copies or substantial portions of the Software.
13 :
14 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 : THE SOFTWARE.
21 : **/
22 :
23 : #include "SPSearchQuery.h"
24 :
25 : namespace STAPPLER_VERSIONIZED stappler::search {
26 :
27 3050 : SearchQuery::SearchQuery(StringView w, uint32_t off, StringView source) : offset(off), value(w.str<memory::PoolInterface>()), source(source) { }
28 :
29 25 : SearchQuery::SearchQuery(SearchOp op, StringView w) : op(op), value(w.str<memory::PoolInterface>()) { }
30 :
31 350 : void SearchQuery::clear() {
32 350 : block = None;
33 350 : offset = 0;
34 350 : op = SearchOp::None;
35 350 : value.clear();
36 350 : args.clear();
37 350 : }
38 :
39 800 : static void SearchQuery_encode_Stappler(const Callback<void(StringView)> &cb, const SearchQuery * t) {
40 800 : if (t->args.empty()) {
41 550 : if (!t->value.empty()) {
42 550 : switch (t->block) {
43 525 : case SearchQuery::None: break;
44 25 : case SearchQuery::Parentesis: cb << "("; break;
45 0 : case SearchQuery::Quoted: cb << "\""; break;
46 : }
47 :
48 550 : if (t->neg) {
49 275 : cb << "!";
50 : }
51 550 : cb << t->value;
52 :
53 550 : switch (t->block) {
54 525 : case SearchQuery::None: break;
55 25 : case SearchQuery::Parentesis: cb << ")"; break;
56 0 : case SearchQuery::Quoted: cb << "\""; break;
57 : }
58 : }
59 : } else {
60 250 : if (!t->args.empty()) {
61 250 : switch (t->block) {
62 100 : case SearchQuery::None: break;
63 100 : case SearchQuery::Parentesis: cb << "("; break;
64 50 : case SearchQuery::Quoted: cb << "\""; break;
65 : }
66 :
67 250 : auto it = t->args.begin();
68 250 : if (t->neg) {
69 75 : cb << "!";
70 : }
71 250 : SearchQuery_encode_Stappler(cb, &(*it));
72 250 : ++ it;
73 :
74 625 : for (;it != t->args.end(); ++ it) {
75 375 : cb << " ";
76 375 : switch (t->op) {
77 250 : case SearchOp::None:
78 : case SearchOp::And:
79 250 : break;
80 75 : case SearchOp::Or: cb << " | "; break;
81 50 : case SearchOp::Follow:
82 50 : if (t->offset > 1 && t->offset <= 5) {
83 0 : for (size_t i = 1; i < t->offset; ++ i) {
84 0 : cb << "a ";
85 : }
86 : }
87 50 : break;
88 : }
89 375 : SearchQuery_encode_Stappler(cb, &(*it));
90 : }
91 :
92 250 : switch (t->block) {
93 100 : case SearchQuery::None: break;
94 100 : case SearchQuery::Parentesis: cb << ")"; break;
95 50 : case SearchQuery::Quoted: cb << "\""; break;
96 : }
97 : }
98 : }
99 800 : }
100 :
101 900 : static void SearchQuery_encode_Postgresql(const Callback<void(StringView)> &cb, const SearchQuery * t) {
102 900 : if (t->args.empty()) {
103 600 : if (!t->value.empty()) {
104 600 : switch (t->block) {
105 575 : case SearchQuery::None: break;
106 25 : case SearchQuery::Parentesis: cb << "("; break;
107 0 : case SearchQuery::Quoted: cb << "("; break;
108 : }
109 :
110 600 : if (t->neg) {
111 300 : cb << "!";
112 : }
113 600 : cb << t->value;
114 : }
115 : } else {
116 300 : if (!t->args.empty()) {
117 300 : if (t->neg) {
118 75 : cb << "!";
119 : }
120 :
121 300 : switch (t->block) {
122 150 : case SearchQuery::None: break;
123 100 : case SearchQuery::Parentesis: cb << "("; break;
124 50 : case SearchQuery::Quoted: cb << "("; break;
125 : }
126 :
127 300 : auto it = t->args.begin();
128 300 : SearchQuery_encode_Postgresql(cb, &(*it));
129 300 : ++ it;
130 :
131 675 : for (;it != t->args.end(); ++ it) {
132 375 : switch (t->op) {
133 0 : case SearchOp::None: cb << " "; break;
134 250 : case SearchOp::And: cb << " & "; break;
135 75 : case SearchOp::Or: cb << " | "; break;
136 50 : case SearchOp::Follow:
137 50 : if (it->offset > 1 && it->offset <= 5) {
138 0 : cb << " <" << uint64_t(it->offset) << "> ";
139 : } else {
140 50 : cb << " <-> ";
141 : }
142 50 : break;
143 : }
144 375 : SearchQuery_encode_Postgresql(cb, &(*it));
145 : }
146 :
147 300 : switch (t->block) {
148 150 : case SearchQuery::None: break;
149 100 : case SearchQuery::Parentesis: cb << ")"; break;
150 50 : case SearchQuery::Quoted: cb << ")"; break;
151 : }
152 : }
153 : }
154 900 : }
155 :
156 400 : void SearchQuery::encode(const Callback<void(StringView)> &cb, Format fmt) const {
157 400 : switch (fmt) {
158 175 : case Stappler: SearchQuery_encode_Stappler(cb, this); break;
159 225 : case Postgresql: SearchQuery_encode_Postgresql(cb, this); break;
160 : }
161 400 : }
162 :
163 675 : static void SearchQuery_print(std::ostream &stream, const SearchQuery * t, uint16_t depth) {
164 675 : if (t->args.empty()) {
165 1650 : for (size_t i = 0; i < depth; ++ i) { stream << " "; }
166 :
167 425 : switch (t->block) {
168 425 : case SearchQuery::None: break;
169 0 : case SearchQuery::Parentesis: stream << "(parentesis) "; break;
170 0 : case SearchQuery::Quoted: stream << "(quoted) "; break;
171 : }
172 :
173 425 : if (t->neg) {
174 125 : stream << "(not) ";
175 : }
176 :
177 425 : if (t->offset > 1) {
178 25 : stream << "<" << t->offset << "> ";
179 : }
180 :
181 425 : if (!t->value.empty()) {
182 425 : stream << "'" << t->value << "'";
183 : }
184 425 : stream << "\n";
185 :
186 : } else {
187 675 : for (size_t i = 0; i < depth; ++ i) { stream << " "; }
188 250 : stream << "-> ";
189 :
190 250 : if (t->neg) {
191 75 : stream << "(not) ";
192 : }
193 :
194 250 : switch (t->block) {
195 75 : case SearchQuery::None: break;
196 100 : case SearchQuery::Parentesis: stream << "(parentesis)"; break;
197 75 : case SearchQuery::Quoted: stream << "(quoted)"; break;
198 : }
199 :
200 250 : switch (t->op) {
201 0 : case SearchOp::None: stream << " (none)"; break;
202 150 : case SearchOp::And: stream << " (and)"; break;
203 25 : case SearchOp::Or: stream << " (or)"; break;
204 75 : case SearchOp::Follow: stream << " (follow)"; break;
205 : }
206 250 : stream << "\n";
207 :
208 850 : for (auto &it : t->args) {
209 600 : SearchQuery_print(stream, &it, depth + 1);
210 : }
211 : }
212 675 : }
213 :
214 75 : void SearchQuery::describe(std::ostream &stream, size_t depth) const {
215 75 : SearchQuery_print(stream, this, depth);
216 75 : }
217 :
218 650 : static void SearchQuery_foreach(const SearchQuery * t, const Callback<void(StringView value, StringView source)> &cb) {
219 650 : if (t->args.empty()) {
220 350 : if (!t->value.empty()) {
221 350 : cb(t->value, t->source);
222 : }
223 : } else {
224 675 : for (auto &it : t->args) {
225 375 : SearchQuery_foreach(&it, cb);
226 : }
227 : }
228 650 : }
229 :
230 275 : void SearchQuery::foreach(const Callback<void(StringView value, StringView source)> &cb) const {
231 275 : SearchQuery_foreach(this, cb);
232 275 : }
233 :
234 : template <typename SearchVectorType>
235 625 : static auto SearchQuery_isMatch(const SearchVectorType &vec, StringView stem) -> const typename SearchVectorType::mapped_type * {
236 625 : auto it = vec.find(stem);
237 625 : if (it != vec.end()) {
238 625 : return &it->second;
239 : }
240 0 : return nullptr;
241 : }
242 :
243 75 : static void SearchQuery_foreachValueMatches(Vector< Pair<SearchData::Rank, Vector<size_t>> > & path, const Vector<Pair<size_t, SearchData::Rank>> &matches) {
244 575 : for (auto &it : matches) {
245 500 : auto &obj = path.emplace_back();
246 500 : obj.first = it.second;
247 500 : obj.second.emplace_back(it.first);
248 : }
249 75 : }
250 :
251 75 : static SpanView<Pair<size_t, SearchData::Rank>> SearchQuery_matchesToArray(const Vector<Pair<size_t, SearchData::Rank>> &matches) {
252 75 : return matches;
253 : }
254 :
255 25 : static void SearchQuery_foreachValueMatches(Vector< Pair<SearchData::Rank, Vector<size_t>> > & path, const Value &matches) {
256 25 : if (!matches.isArray()) {
257 0 : return;
258 : }
259 :
260 25 : auto it = matches.asArray().begin();
261 25 : auto end = matches.asArray().end();
262 :
263 225 : while (it != end) {
264 200 : auto pos = (it ++)->getInteger();
265 200 : auto rank = (it ++)->getInteger();
266 :
267 200 : auto &obj = path.emplace_back();
268 200 : obj.first = SearchRank(rank);
269 200 : obj.second.emplace_back(pos);
270 : }
271 : }
272 :
273 300 : static SpanView<Pair<Value, Value>> SearchQuery_matchesToArray(const Value &matches) {
274 300 : if (matches.isArray()) {
275 300 : auto &arr = matches.asArray();
276 300 : return SpanView<Pair<Value, Value>>((const Pair<Value, Value> *)arr.data(), arr.size() / 2);
277 : }
278 0 : return SpanView<Pair<Value, Value>>();
279 : }
280 :
281 2975 : static int64_t SearchQuery_toInt(const Value &val) {
282 2975 : return val.getInteger();
283 : }
284 :
285 2275 : static int64_t SearchQuery_toInt(const SearchData::Rank &val) {
286 2275 : return toInt(val);
287 : }
288 :
289 9250 : static int64_t SearchQuery_toInt(const size_t &val) {
290 9250 : return val;
291 : }
292 :
293 : template <typename SearchVectorTypeValue>
294 200 : static bool SearchQuery_isFollow(Vector< Pair<SearchData::Rank, Vector<size_t>> > & path,
295 : const SearchVectorTypeValue * v2, size_t offset) {
296 200 : if (offset < 1) {
297 0 : offset = 1;
298 : }
299 :
300 200 : if (path.empty()) {
301 : // add all matches to follow path list
302 100 : SearchQuery_foreachValueMatches(path, *v2);
303 : } else {
304 100 : auto arr = SearchQuery_matchesToArray(*v2);
305 :
306 : // for every known path, check, if next word within range
307 : // if no next word found within range for path - remove path
308 100 : auto it = path.begin();
309 800 : while (it != path.end()) {
310 700 : auto &targetPosition = it->second.back();
311 :
312 : // find closest position of next word
313 700 : auto nextIt = std::lower_bound(arr.begin(), arr.end(), std::make_pair(targetPosition, it->first),
314 2200 : [&] (const auto &l, const Pair<size_t, SearchData::Rank> &r) {
315 2200 : if (SearchQuery_toInt(l.first) != SearchQuery_toInt(r.first)) {
316 2200 : return SearchQuery_toInt(l.first) < SearchQuery_toInt(r.first);
317 : } else {
318 0 : return SearchQuery_toInt(l.second) < SearchQuery_toInt(r.second);
319 : }
320 : });
321 700 : if (nextIt != arr.end()) {
322 : // skip words with other ranks - follow line should have same rank
323 : // also, skip word decompositions (holds same positions in search vector)
324 1250 : while (nextIt != arr.end() &&
325 625 : (SearchQuery_toInt(nextIt->first) == int64_t(targetPosition)
326 625 : || SearchQuery_toInt(nextIt->second) != SearchQuery_toInt(it->first))) {
327 0 : ++ nextIt;
328 : }
329 :
330 1250 : if (nextIt != arr.end() &&
331 625 : (SearchQuery_toInt(nextIt->first) - targetPosition <= offset
332 400 : && SearchQuery_toInt(nextIt->second) == SearchQuery_toInt(it->first))) {
333 : #if 0
334 : // handle repeats - next word offset should be calculated from last word in repeat line
335 : auto possibleRepeat = nextIt;
336 : ++ possibleRepeat;
337 : while (possibleRepeat->first == nextIt->first + 1) {
338 : nextIt = possibleRepeat;
339 : ++ possibleRepeat;
340 : }
341 : #endif
342 400 : it->second.emplace_back(SearchQuery_toInt(nextIt->first));
343 400 : ++ it;
344 400 : continue;
345 : }
346 : }
347 300 : it = path.erase(it);
348 : }
349 : }
350 :
351 200 : return !path.empty();
352 : }
353 :
354 : template <typename SearchVectorType>
355 950 : static bool SearchQuery_isMatch(const SearchVectorType &vec, const SearchQuery &q) {
356 950 : if (!q.args.empty()) {
357 525 : switch (q.op) {
358 350 : case SearchOp::None:
359 : case SearchOp::And:
360 800 : for (auto &it : q.args) {
361 450 : if (!SearchQuery_isMatch(vec, it)) {
362 0 : return q.neg;
363 : break;
364 : }
365 : }
366 350 : return !q.neg;
367 : break;
368 75 : case SearchOp::Or:
369 75 : for (auto &it : q.args) {
370 75 : if (SearchQuery_isMatch(vec, it)) {
371 75 : return !q.neg;
372 : break;
373 : }
374 : }
375 0 : return q.neg;
376 : break;
377 100 : case SearchOp::Follow:
378 100 : Vector< Pair<SearchData::Rank, Vector<size_t>> > path;
379 300 : for (auto &it : q.args) {
380 200 : auto tmp = SearchQuery_isMatch(vec, it.value);
381 200 : if (!tmp) {
382 0 : return q.neg;
383 : }
384 :
385 200 : if (!SearchQuery_isFollow(path, tmp, it.offset)) {
386 0 : return q.neg;
387 : }
388 : }
389 100 : return !q.neg;
390 : break;
391 100 : }
392 425 : } else if (!q.value.empty()) {
393 425 : auto v = SearchQuery_isMatch(vec, q.value);
394 425 : if (q.neg) {
395 0 : return v == nullptr;
396 : } else {
397 425 : return v != nullptr;
398 : }
399 : }
400 0 : return false;
401 : }
402 :
403 125 : bool SearchQuery::isMatch(const SearchVector &vec) const {
404 125 : return SearchQuery_isMatch(vec.words, *this);
405 : }
406 :
407 300 : bool SearchQuery::isMatch(const BytesView &blob) const {
408 300 : auto p = pool::create(pool::acquire());
409 :
410 300 : bool result = false;
411 300 : perform([&, this] {
412 300 : auto d = data::read<Interface>(blob);
413 300 : if (d.isArray() && d.size() == 3 && d.getInteger(0) == 1) {
414 300 : auto &dict = d.getDict(2);
415 300 : result = SearchQuery_isMatch(dict, *this);
416 : }
417 300 : }, p);
418 :
419 300 : pool::destroy(p);
420 300 : return result;
421 : }
422 :
423 75 : static SpanView<Pair<size_t, SearchData::Rank>> SearchQuery_getWordInfo(const SearchVector &vec, StringView word) {
424 75 : auto it = vec.words.find(word);
425 75 : if (it != vec.words.end()) {
426 75 : return it->second;
427 : }
428 0 : return SpanView<Pair<size_t, SearchData::Rank>>();
429 : }
430 :
431 275 : static SpanView<Pair<Value, Value>> SearchQuery_getWordInfo(const Value::DictionaryType &vec, StringView word) {
432 275 : auto it = vec.find(word);
433 275 : if (it != vec.end()) {
434 275 : return SearchQuery_matchesToArray(it->second);
435 : }
436 0 : return SpanView<Pair<Value, Value>>();
437 : }
438 :
439 : template <typename SearchVectorType>
440 350 : static float SearchQuery_rankWord(const SearchVectorType &vec, StringView word, size_t docLength, const RankingValues &vals) {
441 350 : float accum = 0.0f;
442 350 : auto w = SearchQuery_getWordInfo(vec, word);
443 :
444 1350 : for (auto &it : w) {
445 1000 : auto wordPos = float(SearchQuery_toInt(it.first)) / float(docLength);
446 :
447 1000 : accum += vals.rank(SearchRank(SearchQuery_toInt(it.second))) * math::lerp(1.0f, vals.positionFactor, wordPos);
448 : }
449 350 : return accum;
450 : }
451 :
452 : template <typename SearchVectorType>
453 275 : static float SearchQuery_rankQuery(const SearchQuery &query, const SearchVectorType &vec, Normalization norm, const RankingValues &vals,
454 : size_t docLength, size_t wordsCount) {
455 275 : float accum = 0.0f;
456 :
457 975 : query.foreach([&] (StringView word, StringView source) {
458 350 : accum += SearchQuery_rankWord(vec, word, docLength, vals);
459 : });
460 :
461 275 : if ((norm & Normalization::DocLengthLog) != Normalization::Default) {
462 25 : accum /= 1.0f + std::log(float(docLength));
463 : }
464 :
465 275 : if ((norm & Normalization::DocLength) != Normalization::Default) {
466 25 : accum /= (float(docLength));
467 : }
468 :
469 275 : if ((norm & Normalization::UniqueWordsCount) != Normalization::Default) {
470 25 : accum /= (float(wordsCount));
471 : }
472 :
473 275 : if ((norm & Normalization::UniqueWordsCountLog) != Normalization::Default) {
474 25 : accum /= 1.0f + std::log(float(wordsCount));
475 : }
476 :
477 275 : if ((norm & Normalization::Self) != Normalization::Default) {
478 25 : accum /= accum + 1.0f;
479 : }
480 :
481 275 : return accum;
482 : }
483 :
484 25 : float SearchQuery::rankQuery(const SearchVector &vec, Normalization norm, RankingValues vals) const {
485 25 : return SearchQuery_rankQuery(*this, vec, norm, vals, vec.documentLength, vec.words.size());
486 : }
487 :
488 250 : float SearchQuery::rankQuery(const BytesView &blob, Normalization norm, RankingValues vals) const {
489 250 : auto p = pool::create(pool::acquire());
490 :
491 250 : float result = 0.0f;
492 250 : perform([&, this] {
493 250 : auto d = data::read<Interface>(blob);
494 250 : if (d.isArray() && d.size() == 3 && d.getInteger(0) == 1) {
495 250 : auto docLength = d.getInteger(1);
496 250 : auto &dict = d.getDict(2);
497 250 : auto wordsCount = dict.size();
498 250 : result = SearchQuery_rankQuery(*this, dict, norm, vals, docLength, wordsCount);
499 : }
500 250 : }, p);
501 :
502 250 : pool::destroy(p);
503 250 : return result;
504 : }
505 :
506 1200 : void SearchQuery::normalize() {
507 1200 : if (!args.empty() && neg) {
508 50 : switch (op) {
509 25 : case SearchOp::And:
510 25 : neg = false;
511 25 : op = SearchOp::Or;
512 75 : for (auto &it : args) {
513 50 : it.neg = !it.neg;
514 : }
515 25 : break;
516 25 : case SearchOp::Or:
517 25 : neg = false;
518 25 : op = SearchOp::And;
519 75 : for (auto &it : args) {
520 50 : it.neg = !it.neg;
521 : }
522 25 : break;
523 0 : default:
524 0 : break;
525 : }
526 : }
527 1200 : }
528 :
529 600 : static void SearchQuery_decomposeDnf(const SearchQuery &q, const Callback<void(StringView)> &positive, const Callback<void(StringView)> &negative) {
530 600 : if (!q.value.empty()) {
531 475 : positive(q.value);
532 : } else {
533 375 : for (auto &it : q.args) {
534 250 : SearchQuery_decomposeDnf(it, positive, negative);
535 : }
536 : }
537 600 : }
538 :
539 200 : static void SearchQuery_decomposeCnf(const SearchQuery &q, const Callback<void(StringView)> &positive, const Callback<void(StringView)> &negative) {
540 200 : if (!q.value.empty()) {
541 25 : if (q.neg) {
542 25 : negative(q.value);
543 : } else {
544 0 : positive(q.value);
545 : }
546 : } else {
547 575 : for (auto &it : q.args) {
548 400 : switch(q.op) {
549 250 : case SearchOp::And:
550 : case SearchOp::Follow:
551 250 : if (!it.neg) {
552 225 : SearchQuery_decomposeDnf(it, positive, negative);
553 : } else {
554 25 : SearchQuery_decomposeCnf(it, positive, negative);
555 : }
556 250 : break;
557 150 : case SearchOp::Or:
558 150 : if (!it.value.empty()) {
559 150 : if (!it.neg) {
560 100 : positive(it.value);
561 : }
562 : } else {
563 0 : SearchQuery_decomposeDnf(it, positive, negative);
564 : }
565 150 : break;
566 0 : case SearchOp::None:
567 0 : break;
568 : }
569 : }
570 : }
571 200 : }
572 :
573 525 : void SearchQuery::decompose(const Callback<void(StringView)> &positive, const Callback<void(StringView)> &negative) const {
574 525 : if (!args.empty()) {
575 1325 : for (auto &it : args) {
576 850 : switch(op) {
577 750 : case SearchOp::And:
578 : case SearchOp::Follow:
579 750 : if (!it.value.empty()) {
580 450 : if (it.neg) {
581 125 : negative(it.value);
582 : } else {
583 325 : positive(it.value);
584 : }
585 300 : } else if (it.neg) {
586 125 : SearchQuery_decomposeDnf(it, positive, negative);
587 : } else {
588 175 : SearchQuery_decomposeCnf(it, positive, negative);
589 : }
590 750 : break;
591 100 : case SearchOp::Or:
592 100 : if (!it.value.empty()) {
593 100 : if (!it.neg) {
594 50 : positive(it.value);
595 : }
596 : } else {
597 0 : SearchQuery_decomposeDnf(it, positive, negative);
598 : }
599 100 : break;
600 0 : case SearchOp::None:
601 0 : break;
602 : }
603 : }
604 : } else {
605 50 : if (neg) {
606 25 : negative(value);
607 : } else {
608 25 : positive(value);
609 : }
610 : }
611 525 : }
612 :
613 : }
|
