xref: /dokuwiki/inc/Search/FulltextSearch.php (revision 677f78a7ff09e4a1003aad73df5a269fc6e9f8ee) 
1<?php
2namespace dokuwiki\Search;
3
4use dokuwiki\Extension\Event;
5use dokuwiki\Search\Indexer;
6use dokuwiki\Search\QueryParser;
7use dokuwiki\Utf8;
8
9/**
10 * Class DokuWiki Fulltext Search
11 *
12 * @license    GPL 2 (http://www.gnu.org/licenses/gpl.html)
13 * @author     Andreas Gohr <andi@splitbrain.org>
14 */
15class FulltextSearch
16{
17    /**
18     *  Fulltext Search constructor. prevent direct object creation
19     */
20    protected function __construct() {}
21
22    /**
23     * The fulltext search
24     *
25     * Returns a list of matching documents for the given query
26     *
27     * refactored into ft_pageSearch(), _ft_pageSearch() and trigger_event()
28     *
29     * @param string     $query
30     * @param array      $highlight
31     * @param string     $sort
32     * @param int|string $after  only show results with mtime after this date,
33     *                           accepts timestap or strtotime arguments
34     * @param int|string $before only show results with mtime before this date,
35     *                           accepts timestap or strtotime arguments
36     *
37     * @return array
38     */
39    public static function pageSearch($query, &$highlight, $sort = null, $after = null, $before = null)
40    {
41        if ($sort === null) {
42            $sort = 'hits';
43        }
44        $data = [
45            'query' => $query,
46            'sort' => $sort,
47            'after' => $after,
48            'before' => $before
49        ];
50        $data['highlight'] =& $highlight;
51        $action = static::class.'::callback_pageSearch';
52        return Event::createAndTrigger('SEARCH_QUERY_FULLPAGE', $data, $action);
53    }
54
55    /**
56     * Returns a list of matching documents for the given query
57     *
58     * @author Andreas Gohr <andi@splitbrain.org>
59     * @author Kazutaka Miyasaka <kazmiya@gmail.com>
60     *
61     * @param array $data  event data
62     * @return array       matching documents
63     */
64    public static function callback_pageSearch(&$data)
65    {
66        $Indexer = Indexer::getInstance();
67
68        // parse the given query
69        $q = QueryParser::convert($data['query']);
70        $data['highlight'] = $q['highlight'];
71
72        if (empty($q['parsed_ary'])) return array();
73
74        // lookup all words found in the query
75        $lookup = $Indexer->lookup($q['words']);
76
77        // get all pages in this dokuwiki site (!: includes nonexistent pages)
78        $pages_all = array();
79        foreach ($Indexer->getPages() as $id) {
80            $pages_all[$id] = 0; // base: 0 hit
81        }
82
83        // process the query
84        $stack = array();
85        foreach ($q['parsed_ary'] as $token) {
86            switch (substr($token, 0, 3)) {
87                case 'W+:':
88                case 'W-:':
89                case 'W_:': // word
90                    $word    = substr($token, 3);
91                    $stack[] = (array) $lookup[$word];
92                    break;
93                case 'P+:':
94                case 'P-:': // phrase
95                    $phrase = substr($token, 3);
96                    // since phrases are always parsed as ((W1)(W2)...(P)),
97                    // the end($stack) always points the pages that contain
98                    // all words in this phrase
99                    $pages  = end($stack);
100                    $pages_matched = array();
101                    foreach (array_keys($pages) as $id) {
102                        $evdata = array(
103                            'id' => $id,
104                            'phrase' => $phrase,
105                            'text' => rawWiki($id)
106                        );
107                        $evt = new Event('FULLTEXT_PHRASE_MATCH', $evdata);
108                        if ($evt->advise_before() && $evt->result !== true) {
109                            $text = Utf8\PhpString::strtolower($evdata['text']);
110                            if (strpos($text, $phrase) !== false) {
111                                $evt->result = true;
112                            }
113                        }
114                        $evt->advise_after();
115                        if ($evt->result === true) {
116                            $pages_matched[$id] = 0; // phrase: always 0 hit
117                        }
118                    }
119                    $stack[] = $pages_matched;
120                    break;
121                case 'N+:':
122                case 'N-:': // namespace
123                    $ns = cleanID(substr($token, 3)) . ':';
124                    $pages_matched = array();
125                    foreach (array_keys($pages_all) as $id) {
126                        if (strpos($id, $ns) === 0) {
127                            $pages_matched[$id] = 0; // namespace: always 0 hit
128                        }
129                    }
130                    $stack[] = $pages_matched;
131                    break;
132                case 'AND': // and operation
133                    list($pages1, $pages2) = array_splice($stack, -2);
134                    $stack[] = static::resultCombine(array($pages1, $pages2));
135                    break;
136                case 'OR':  // or operation
137                    list($pages1, $pages2) = array_splice($stack, -2);
138                    $stack[] = static::resultUnite(array($pages1, $pages2));
139                    break;
140                case 'NOT': // not operation (unary)
141                    $pages   = array_pop($stack);
142                    $stack[] = static::resultComplement(array($pages_all, $pages));
143                    break;
144            }
145        }
146        $docs = array_pop($stack);
147
148        if (empty($docs)) return array();
149
150        // check: settings, acls, existence
151        foreach (array_keys($docs) as $id) {
152            if (isHiddenPage($id)
153                || auth_quickaclcheck($id) < AUTH_READ
154                || !page_exists($id, '', false)
155            ) {
156                unset($docs[$id]);
157            }
158        }
159
160        $docs = static::filterResultsByTime($docs, $data['after'], $data['before']);
161
162        if ($data['sort'] === 'mtime') {
163            uksort($docs, static::class.'::pagemtimesorter');
164        } else {
165            // sort docs by count
166            arsort($docs);
167        }
168
169        return $docs;
170    }
171
172    /**
173     * @param array      $results search results in the form pageid => value
174     * @param int|string $after   only returns results with mtime after this date,
175     *                            accepts timestap or strtotime arguments
176     * @param int|string $before  only returns results with mtime after this date,
177     *                            accepts timestap or strtotime arguments
178     *
179     * @return array
180     */
181    protected static function filterResultsByTime(array $results, $after, $before)
182    {
183        if ($after || $before) {
184            $after = is_int($after) ? $after : strtotime($after);
185            $before = is_int($before) ? $before : strtotime($before);
186
187            foreach ($results as $id => $value) {
188                $mTime = filemtime(wikiFN($id));
189                if ($after && $after > $mTime) {
190                    unset($results[$id]);
191                    continue;
192                }
193                if ($before && $before < $mTime) {
194                    unset($results[$id]);
195                }
196            }
197        }
198        return $results;
199    }
200
201    /**
202     * Sort pages by their mtime, from newest to oldest
203     *
204     * @param string $a
205     * @param string $b
206     *
207     * @return int Returns < 0 if $a is newer than $b, > 0 if $b is newer than $a
208     *             and 0 if they are of the same age
209     */
210    protected static function pagemtimesorter($a, $b)
211    {
212        $mtimeA = filemtime(wikiFN($a));
213        $mtimeB = filemtime(wikiFN($b));
214        return $mtimeB - $mtimeA;
215    }
216
217    /**
218     * Creates a snippet extract
219     *
220     * @author Andreas Gohr <andi@splitbrain.org>
221     * @triggers FULLTEXT_SNIPPET_CREATE
222     *
223     * @param string $id page id
224     * @param array $highlight
225     * @return mixed
226     */
227    public static function snippet($id, $highlight)
228    {
229        $text = rawWiki($id);
230        $text = str_replace("\xC2\xAD",'',$text); // remove soft-hyphens
231        $evdata = array(
232            'id'        => $id,
233            'text'      => &$text,
234            'highlight' => &$highlight,
235            'snippet'   => '',
236        );
237
238        $evt = new Event('FULLTEXT_SNIPPET_CREATE', $evdata);
239        if ($evt->advise_before()) {
240            $match = array();
241            $snippets = array();
242            $utf8_offset = $offset = $end = 0;
243            $len = Utf8\PhpString::strlen($text);
244
245            // build a regexp from the phrases to highlight
246            $re1 = '(' .
247                join(
248                    '|',
249                    array_map(
250                        static::class.'::snippet_re_preprocess',
251                        array_map(
252                            'preg_quote_cb',
253                            array_filter((array) $highlight)
254                        )
255                    )
256                ) .
257                ')';
258            $re2 = "$re1.{0,75}(?!\\1)$re1";
259            $re3 = "$re1.{0,45}(?!\\1)$re1.{0,45}(?!\\1)(?!\\2)$re1";
260
261            for ($cnt=4; $cnt--;) {
262                if (0) {
263                } elseif (preg_match('/'.$re3.'/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
264                } elseif (preg_match('/'.$re2.'/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
265                } elseif (preg_match('/'.$re1.'/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
266                } else {
267                    break;
268                }
269
270                list($str, $idx) = $match[0];
271
272                // convert $idx (a byte offset) into a utf8 character offset
273                $utf8_idx = Utf8\PhpString::strlen(substr($text, 0, $idx));
274                $utf8_len = Utf8\PhpString::strlen($str);
275
276                // establish context, 100 bytes surrounding the match string
277                // first look to see if we can go 100 either side,
278                // then drop to 50 adding any excess if the other side can't go to 50,
279                $pre = min($utf8_idx - $utf8_offset, 100);
280                $post = min($len - $utf8_idx - $utf8_len, 100);
281
282                if ($pre > 50 && $post > 50) {
283                    $pre = $post = 50;
284                } elseif ($pre > 50) {
285                    $pre = min($pre, 100 - $post);
286                } elseif ($post > 50) {
287                    $post = min($post, 100 - $pre);
288                } elseif ($offset == 0) {
289                    // both are less than 50, means the context is the whole string
290                    // make it so and break out of this loop - there is no need for the
291                    // complex snippet calculations
292                    $snippets = array($text);
293                    break;
294                }
295
296                // establish context start and end points, try to append to previous
297                // context if possible
298                $start = $utf8_idx - $pre;
299                $append = ($start < $end) ? $end : false;  // still the end of the previous context snippet
300                $end = $utf8_idx + $utf8_len + $post;      // now set it to the end of this context
301
302                if ($append) {
303                    $snippets[count($snippets)-1] .= Utf8\PhpString::substr($text, $append, $end-$append);
304                } else {
305                    $snippets[] = Utf8\PhpString::substr($text, $start, $end-$start);
306                }
307
308                // set $offset for next match attempt
309                // continue matching after the current match
310                // if the current match is not the longest possible match starting at the current offset
311                // this prevents further matching of this snippet but for possible matches of length
312                // smaller than match length + context (at least 50 characters) this match is part of the context
313                $utf8_offset = $utf8_idx + $utf8_len;
314                $offset = $idx + strlen(Utf8\PhpString::substr($text, $utf8_idx, $utf8_len));
315                $offset = Utf8\Clean::correctIdx($text, $offset);
316            }
317
318            $m = "\1";
319            $snippets = preg_replace('/'.$re1.'/iu', $m.'$1'.$m, $snippets);
320            $snippet = preg_replace(
321                '/' . $m . '([^' . $m . ']*?)' . $m . '/iu',
322                '<strong class="search_hit">$1</strong>',
323                hsc(join('... ', $snippets))
324            );
325
326            $evdata['snippet'] = $snippet;
327        }
328        $evt->advise_after();
329        unset($evt);
330
331        return $evdata['snippet'];
332    }
333
334    /**
335     * Wraps a search term in regex boundary checks.
336     *
337     * @param string $term
338     * @return string
339     */
340    public static function snippet_re_preprocess($term)
341    {
342        // do not process asian terms where word boundaries are not explicit
343        if (Utf8\Asian::isAsianWords($term)) return $term;
344
345        if (UTF8_PROPERTYSUPPORT) {
346            // unicode word boundaries
347            // see http://stackoverflow.com/a/2449017/172068
348            $BL = '(?<!\pL)';
349            $BR = '(?!\pL)';
350        } else {
351            // not as correct as above, but at least won't break
352            $BL = '\b';
353            $BR = '\b';
354        }
355
356        if (substr($term, 0, 2) == '\\*') {
357            $term = substr($term, 2);
358        } else {
359            $term = $BL.$term;
360        }
361
362        if (substr($term, -2, 2) == '\\*') {
363            $term = substr($term, 0, -2);
364        } else {
365            $term = $term.$BR;
366        }
367
368        if ($term == $BL || $term == $BR || $term == $BL.$BR) {
369            $term = '';
370        }
371        return $term;
372    }
373
374    /**
375     * Combine found documents and sum up their scores
376     *
377     * This function is used to combine searched words with a logical
378     * AND. Only documents available in all arrays are returned.
379     *
380     * based upon PEAR's PHP_Compat function for array_intersect_key()
381     *
382     * @param array $args An array of page arrays
383     * @return array
384     */
385    protected static function resultCombine($args)
386    {
387        $array_count = count($args);
388        if ($array_count == 1) {
389            return $args[0];
390        }
391
392        $result = array();
393        if ($array_count > 1) {
394            foreach ($args[0] as $key => $value) {
395                $result[$key] = $value;
396                for ($i = 1; $i !== $array_count; $i++) {
397                    if (!isset($args[$i][$key])) {
398                        unset($result[$key]);
399                        break;
400                    }
401                    $result[$key] += $args[$i][$key];
402                }
403            }
404        }
405        return $result;
406    }
407
408    /**
409     * Unites found documents and sum up their scores
410     * based upon resultCombine() method
411     *
412     * @param array $args An array of page arrays
413     * @return array
414     *
415     * @author Kazutaka Miyasaka <kazmiya@gmail.com>
416     */
417    protected static function resultUnite($args)
418    {
419        $array_count = count($args);
420        if ($array_count === 1) {
421            return $args[0];
422        }
423
424        $result = $args[0];
425        for ($i = 1; $i !== $array_count; $i++) {
426            foreach (array_keys($args[$i]) as $id) {
427                $result[$id] += $args[$i][$id];
428            }
429        }
430        return $result;
431    }
432
433    /**
434     * Computes the difference of documents using page id for comparison
435     * nearly identical to PHP5's array_diff_key()
436     *
437     * @param array $args An array of page arrays
438     * @return array
439     *
440     * @author Kazutaka Miyasaka <kazmiya@gmail.com>
441     */
442    protected static function resultComplement($args)
443    {
444        $array_count = count($args);
445        if ($array_count === 1) {
446            return $args[0];
447        }
448
449        $result = $args[0];
450        foreach (array_keys($result) as $id) {
451            for ($i = 1; $i !== $array_count; $i++) {
452                if (isset($args[$i][$id])) unset($result[$id]);
453            }
454        }
455        return $result;
456    }
457}
458