xref: /dokuwiki/inc/Search/Query/QueryEvaluator.php (revision 2d05a06d7893e8c100d5357c6301ffae08b00522) 
1<?php
2
3namespace dokuwiki\Search\Query;
4
5use dokuwiki\Utf8\PhpString;
6use dokuwiki\Extension\Event;
7use dokuwiki\Search\Collection\Term;
8use dokuwiki\Search\Indexer;
9use dokuwiki\Utf8;
10
11/**
12 * Evaluates a parsed search query against word lookup results
13 *
14 * Uses typed stack entries (PageSet, NamespacePredicate, NegatedEntry)
15 * to avoid materializing the full page index unless absolutely necessary
16 * (standalone NOT or namespace-only queries).
17 */
18class QueryEvaluator
19{
20    /** @var string[] RPN token array from QueryParser */
21    protected array $rpn;
22
23    /** @var Term[] word => Term mapping from CollectionSearch */
24    protected array $terms;
25
26    /** @var PageSet|null lazy-loaded universe of all indexed pages */
27    protected ?PageSet $allPages = null;
28
29    /**
30     * @param string[] $rpn RPN token array from QueryParser::convert()['parsed_ary']
31     * @param Term[] $terms word => Term mapping from CollectionSearch::execute()
32     */
33    public function __construct(array $rpn, array $terms)
34    {
35        $this->rpn = $rpn;
36        $this->terms = $terms;
37    }
38
39    /**
40     * Evaluate the RPN query and return matching pages with scores
41     *
42     * The query is represented in Reverse Polish Notation (RPN), also known as postfix
43     * notation. In RPN, operands come first and operators follow. For example, the infix
44     * expression "A AND B" becomes "A B AND" in RPN. This eliminates the need for
45     * parentheses — the expression "(A OR B) AND C" is simply "A B OR C AND".
46     *
47     * Evaluation uses a stack. Each token is processed left to right: operand tokens
48     * (words, phrases, namespaces) push an entry onto the stack; operator tokens (AND,
49     * OR, NOT) pop their operands from the stack, compute a result, and push it back.
50     * After all tokens are processed, the single remaining stack entry is the final result.
51     *
52     * The stack entries are typed: word lookups produce PageSet entries (concrete page
53     * results with scores), namespace tokens produce NamespacePredicate entries (a filter
54     * to be applied later), and NOT wraps its operand in a NegatedEntry. Binary operators
55     * inspect the types of their operands to choose the most efficient operation — for
56     * example, AND with a NegatedEntry performs set subtraction rather than requiring
57     * the full page universe.
58     *
59     * @return array<string, int> page ID => score
60     */
61    public function evaluate(): array
62    {
63        /** @var StackEntry[] $stack */
64        $stack = [];
65
66        foreach ($this->rpn as $token) {
67            switch (substr($token, 0, 3)) {
68                case 'W+:':
69                case 'W-:':
70                case 'W_:':
71                    $word = substr($token, 3);
72                    if (isset($this->terms[$word])) {
73                        $stack[] = new PageSet($this->terms[$word]->getEntityFrequencies());
74                    }
75                    break;
76
77                case 'P+:':
78                case 'P-:':
79                    $phrase = substr($token, 3);
80                    // Phrases are always preceded by their component words AND'd together,
81                    // so the top of stack contains pages matching all words in the phrase.
82                    // We verify the actual phrase exists in those candidate pages.
83                    $candidates = end($stack) ?: new PageSet();
84                    $stack[] = $this->matchPhrase($phrase, $this->materialize($candidates));
85                    break;
86
87                case 'N+:':
88                case 'N-:':
89                    $ns = cleanID(substr($token, 3)) . ':';
90                    $stack[] = new NamespacePredicate($ns);
91                    break;
92
93                case 'AND':
94                    $right = array_pop($stack);
95                    $left = array_pop($stack);
96                    if (!$left && !$right) break;
97                    if (!$left) {
98                        $stack[] = $right;
99                        break;
100                    }
101                    if (!$right) {
102                        $stack[] = $left;
103                        break;
104                    }
105                    $stack[] = $this->opAnd($left, $right);
106                    break;
107
108                case 'OR':
109                    $right = array_pop($stack);
110                    $left = array_pop($stack);
111                    if (!$left && !$right) break;
112                    if (!$left) {
113                        $stack[] = $right;
114                        break;
115                    }
116                    if (!$right) {
117                        $stack[] = $left;
118                        break;
119                    }
120                    $stack[] = $this->opOr($left, $right);
121                    break;
122
123                case 'NOT':
124                    $operand = array_pop($stack);
125                    if (!$operand) break;
126                    $stack[] = new NegatedEntry($operand);
127                    break;
128            }
129        }
130
131        $result = array_pop($stack) ?? new PageSet();
132        return $this->materialize($result)->getPages();
133    }
134
135    // region Operators
136
137    /**
138     * AND: combine two operands based on their types
139     *
140     * PageSet AND PageSet produces an intersection with summed scores. When one
141     * operand is a NegatedEntry, the operation becomes set subtraction. When one
142     * operand is a NamespacePredicate, the other is filtered by namespace prefix.
143     *
144     * @param StackEntry $left
145     * @param StackEntry $right
146     * @return StackEntry
147     */
148    protected function opAnd(StackEntry $left, StackEntry $right): StackEntry
149    {
150        // page set AND negated → subtract
151        if ($left instanceof PageSet && $right instanceof NegatedEntry) {
152            return $this->subtractNegated($left, $right);
153        }
154        if ($left instanceof NegatedEntry && $right instanceof PageSet) {
155            return $this->subtractNegated($right, $left);
156        }
157
158        // page set AND namespace → filter by prefix
159        if ($left instanceof PageSet && $right instanceof NamespacePredicate) {
160            return $right->filter($left);
161        }
162        if ($left instanceof NamespacePredicate && $right instanceof PageSet) {
163            return $left->filter($right);
164        }
165
166        // page set AND page set → intersect, sum scores
167        if ($left instanceof PageSet && $right instanceof PageSet) {
168            return $left->intersect($right);
169        }
170
171        // rare cases (negated AND negated, namespace AND namespace, etc.)
172        return $this->materialize($left)->intersect($this->materialize($right));
173    }
174
175    /**
176     * OR: unite two operands
177     *
178     * PageSet OR PageSet produces a union with summed scores. Other combinations
179     * require materializing operands into concrete page sets first.
180     *
181     * @param StackEntry $left
182     * @param StackEntry $right
183     * @return StackEntry
184     */
185    protected function opOr(StackEntry $left, StackEntry $right): StackEntry
186    {
187        if ($left instanceof PageSet && $right instanceof PageSet) {
188            return $left->unite($right);
189        }
190
191        return $this->materialize($left)->unite($this->materialize($right));
192    }
193
194    /**
195     * Subtract a NegatedEntry from a PageSet
196     *
197     * The inner entry of the NegatedEntry determines the operation:
198     * - NegatedEntry(PageSet): set subtraction
199     * - NegatedEntry(NamespacePredicate): exclude pages matching the namespace
200     *
201     * @param PageSet $pages the positive page set
202     * @param NegatedEntry $negated the negated operand
203     * @return PageSet
204     */
205    protected function subtractNegated(PageSet $pages, NegatedEntry $negated): PageSet
206    {
207        $inner = $negated->getInner();
208
209        if ($inner instanceof NamespacePredicate) {
210            return $inner->exclude($pages);
211        }
212
213        return $pages->subtract($this->materialize($inner));
214    }
215
216    // endregion
217
218    // region Phrase matching
219
220    /**
221     * Check which pages from the candidate set contain the given phrase
222     *
223     * Verifies phrase presence by reading each page's raw wiki text.
224     * Plugins can override phrase matching via the FULLTEXT_PHRASE_MATCH event.
225     * Pages that match retain their original scores from the candidate set.
226     *
227     * @param string $phrase the phrase to search for
228     * @param PageSet $candidates pages to check (typically the AND'd word results)
229     * @return PageSet pages where the phrase was found, with original scores preserved
230     */
231    protected function matchPhrase(string $phrase, PageSet $candidates): PageSet
232    {
233        $matched = [];
234        foreach ($candidates->getPages() as $id => $score) {
235            $evdata = [
236                'id' => $id,
237                'phrase' => $phrase,
238                'text' => rawWiki($id),
239            ];
240            $event = new Event('FULLTEXT_PHRASE_MATCH', $evdata);
241            if ($event->advise_before() && $event->result !== true) {
242                $text = PhpString::strtolower($evdata['text']);
243                if (str_contains($text, $phrase)) {
244                    $event->result = true;
245                }
246            }
247            $event->advise_after();
248            if ($event->result === true) {
249                $matched[$id] = $score;
250            }
251        }
252        return new PageSet($matched);
253    }
254
255    // endregion
256
257    // region Materialization
258
259    /**
260     * Convert any StackEntry into a concrete PageSet
261     *
262     * For PageSet entries, returns as-is. NamespacePredicate and NegatedEntry
263     * cannot be resolved without knowing all existing pages — a namespace
264     * predicate needs the full page list to find matching pages, and a negated
265     * entry needs it to compute the complement. This is why materialization
266     * triggers a lazy-load of the full page index from disk.
267     *
268     * This is only needed for standalone namespace or negative-only queries
269     * (e.g., just "@wiki:" or just "-foo"). In combined queries, the typed
270     * operators handle these entries without the universe.
271     *
272     * @param StackEntry $entry
273     * @return PageSet
274     */
275    protected function materialize(StackEntry $entry): PageSet
276    {
277        if ($entry instanceof PageSet) {
278            return $entry;
279        }
280
281        if ($entry instanceof NegatedEntry) {
282            return $this->getAllPages()->subtract($this->materialize($entry->getInner()));
283        }
284
285        if ($entry instanceof NamespacePredicate) {
286            return $entry->filter($this->getAllPages());
287        }
288
289        return new PageSet();
290    }
291
292    /**
293     * Lazy-load the universe of all indexed pages
294     *
295     * @return PageSet all pages with score 0
296     */
297    protected function getAllPages(): PageSet
298    {
299        if (!$this->allPages instanceof PageSet) {
300            $pages = (new Indexer())->getAllPages();
301            $this->allPages = new PageSet(array_fill_keys($pages, 0));
302        }
303        return $this->allPages;
304    }
305
306    // endregion
307}
308