xref: /dokuwiki/inc/fulltext.php (revision fe15e2c063a38f65804c55e581c72b96ac36edf7) 
1<?php
2/**
3 * DokuWiki fulltextsearch functions using the index
4 *
5 * @license    GPL 2 (http://www.gnu.org/licenses/gpl.html)
6 * @author     Andreas Gohr <andi@splitbrain.org>
7 */
8use dokuwiki\Utf8\Asian;
9use dokuwiki\Search\Indexer;
10use dokuwiki\Extension\Event;
11use dokuwiki\Utf8\Clean;
12use dokuwiki\Utf8\PhpString;
13use dokuwiki\Utf8\Sort;
14
15/**
16 * create snippets for the first few results only
17 */
18if (!defined('FT_SNIPPET_NUMBER')) define('FT_SNIPPET_NUMBER', 15);
19
20/**
21 * The fulltext search
22 *
23 * Returns a list of matching documents for the given query
24 *
25 * refactored into ft_pageSearch(), _ft_pageSearch() and trigger_event()
26 *
27 * @param string     $query
28 * @param array      $highlight
29 * @param string     $sort
30 * @param int|string $after  only show results with mtime after this date, accepts timestap or strtotime arguments
31 * @param int|string $before only show results with mtime before this date, accepts timestap or strtotime arguments
32 *
33 * @return array
34 */
35function ft_pageSearch($query, &$highlight, $sort = null, $after = null, $before = null)
36{
37
38    if ($sort === null) {
39        $sort = 'hits';
40    }
41    $data = [
42        'query' => $query,
43        'sort' => $sort,
44        'after' => $after,
45        'before' => $before
46    ];
47    $data['highlight'] =& $highlight;
48
49    return Event::createAndTrigger('SEARCH_QUERY_FULLPAGE', $data, '_ft_pageSearch');
50}
51
52/**
53 * Returns a list of matching documents for the given query
54 *
55 * @author Andreas Gohr <andi@splitbrain.org>
56 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
57 *
58 * @param array $data event data
59 * @return array matching documents
60 */
61function _ft_pageSearch(&$data)
62{
63    $Indexer = idx_get_indexer();
64
65    // parse the given query
66    $q = ft_queryParser($Indexer, $data['query']);
67    $data['highlight'] = $q['highlight'];
68
69    if (empty($q['parsed_ary'])) return [];
70
71    // lookup all words found in the query
72    $lookup = $Indexer->lookup($q['words']);
73
74    // get all pages in this dokuwiki site (!: includes nonexistent pages)
75    $pages_all = [];
76    foreach ($Indexer->getPages() as $id) {
77        $pages_all[$id] = 0; // base: 0 hit
78    }
79
80    // process the query
81    $stack = [];
82    foreach ($q['parsed_ary'] as $token) {
83        switch (substr($token, 0, 3)) {
84            case 'W+:':
85            case 'W-:':
86            case 'W_:': // word
87                $word    = substr($token, 3);
88                if (isset($lookup[$word])) {
89                    $stack[] = (array)$lookup[$word];
90                }
91                break;
92            case 'P+:':
93            case 'P-:': // phrase
94                $phrase = substr($token, 3);
95                // since phrases are always parsed as ((W1)(W2)...(P)),
96                // the end($stack) always points the pages that contain
97                // all words in this phrase
98                $pages  = end($stack);
99                $pages_matched = [];
100                foreach (array_keys($pages) as $id) {
101                    $evdata = [
102                        'id' => $id,
103                        'phrase' => $phrase,
104                        'text' => rawWiki($id)
105                    ];
106                    $evt = new Event('FULLTEXT_PHRASE_MATCH', $evdata);
107                    if ($evt->advise_before() && $evt->result !== true) {
108                        $text = PhpString::strtolower($evdata['text']);
109                        if (strpos($text, $phrase) !== false) {
110                            $evt->result = true;
111                        }
112                    }
113                    $evt->advise_after();
114                    if ($evt->result === true) {
115                        $pages_matched[$id] = 0; // phrase: always 0 hit
116                    }
117                }
118                $stack[] = $pages_matched;
119                break;
120            case 'N+:':
121            case 'N-:': // namespace
122                $ns = cleanID(substr($token, 3)) . ':';
123                $pages_matched = [];
124                foreach (array_keys($pages_all) as $id) {
125                    if (strpos($id, $ns) === 0) {
126                        $pages_matched[$id] = 0; // namespace: always 0 hit
127                    }
128                }
129                $stack[] = $pages_matched;
130                break;
131            case 'AND': // and operation
132                [$pages1, $pages2] = array_splice($stack, -2);
133                $stack[] = ft_resultCombine([$pages1, $pages2]);
134                break;
135            case 'OR':  // or operation
136                [$pages1, $pages2] = array_splice($stack, -2);
137                $stack[] = ft_resultUnite([$pages1, $pages2]);
138                break;
139            case 'NOT': // not operation (unary)
140                $pages   = array_pop($stack);
141                $stack[] = ft_resultComplement([$pages_all, $pages]);
142                break;
143        }
144    }
145    $docs = array_pop($stack);
146
147    if (empty($docs)) return [];
148
149    // check: settings, acls, existence
150    foreach (array_keys($docs) as $id) {
151        if (isHiddenPage($id) || auth_quickaclcheck($id) < AUTH_READ || !page_exists($id, '', false)) {
152            unset($docs[$id]);
153        }
154    }
155
156    $docs = _ft_filterResultsByTime($docs, $data['after'], $data['before']);
157
158    if ($data['sort'] === 'mtime') {
159        uksort($docs, 'ft_pagemtimesorter');
160    } else {
161        // sort docs by count
162        uksort($docs, 'ft_pagesorter');
163        arsort($docs);
164    }
165
166    return $docs;
167}
168
169/**
170 * Returns the backlinks for a given page
171 *
172 * Uses the metadata index.
173 *
174 * @param string $id           The id for which links shall be returned
175 * @param bool   $ignore_perms Ignore the fact that pages are hidden or read-protected
176 * @return array The pages that contain links to the given page
177 */
178function ft_backlinks($id, $ignore_perms = false)
179{
180    $result = idx_get_indexer()->lookupKey('relation_references', $id);
181
182    if ($result === []) return $result;
183
184    // check ACL permissions
185    foreach (array_keys($result) as $idx) {
186        if (
187            (!$ignore_perms && (
188                isHiddenPage($result[$idx]) || auth_quickaclcheck($result[$idx]) < AUTH_READ
189            )) || !page_exists($result[$idx], '', false)
190        ) {
191            unset($result[$idx]);
192        }
193    }
194
195    Sort::sort($result);
196    return $result;
197}
198
199/**
200 * Returns the pages that use a given media file
201 *
202 * Uses the relation media metadata property and the metadata index.
203 *
204 * Note that before 2013-07-31 the second parameter was the maximum number of results and
205 * permissions were ignored. That's why the parameter is now checked to be explicitely set
206 * to true (with type bool) in order to be compatible with older uses of the function.
207 *
208 * @param string $id           The media id to look for
209 * @param bool   $ignore_perms Ignore hidden pages and acls (optional, default: false)
210 * @return array A list of pages that use the given media file
211 */
212function ft_mediause($id, $ignore_perms = false)
213{
214    $result = idx_get_indexer()->lookupKey('relation_media', $id);
215
216    if ($result === []) return $result;
217
218    // check ACL permissions
219    foreach (array_keys($result) as $idx) {
220        if (
221            (!$ignore_perms && (
222                    isHiddenPage($result[$idx]) || auth_quickaclcheck($result[$idx]) < AUTH_READ
223                )) || !page_exists($result[$idx], '', false)
224        ) {
225            unset($result[$idx]);
226        }
227    }
228
229    Sort::sort($result);
230    return $result;
231}
232
233
234/**
235 * Quicksearch for pagenames
236 *
237 * By default it only matches the pagename and ignores the
238 * namespace. This can be changed with the second parameter.
239 * The third parameter allows to search in titles as well.
240 *
241 * The function always returns titles as well
242 *
243 * @triggers SEARCH_QUERY_PAGELOOKUP
244 * @author   Andreas Gohr <andi@splitbrain.org>
245 * @author   Adrian Lang <lang@cosmocode.de>
246 *
247 * @param string     $id       page id
248 * @param bool       $in_ns    match against namespace as well?
249 * @param bool       $in_title search in title?
250 * @param int|string $after    only show results with mtime after this date, accepts timestap or strtotime arguments
251 * @param int|string $before   only show results with mtime before this date, accepts timestap or strtotime arguments
252 *
253 * @return string[]
254 */
255function ft_pageLookup($id, $in_ns = false, $in_title = false, $after = null, $before = null)
256{
257    $data = [
258        'id' => $id,
259        'in_ns' => $in_ns,
260        'in_title' => $in_title,
261        'after' => $after,
262        'before' => $before
263    ];
264    $data['has_titles'] = true; // for plugin backward compatibility check
265    return Event::createAndTrigger('SEARCH_QUERY_PAGELOOKUP', $data, '_ft_pageLookup');
266}
267
268/**
269 * Returns list of pages as array(pageid => First Heading)
270 *
271 * @param array &$data event data
272 * @return string[]
273 */
274function _ft_pageLookup(&$data)
275{
276    // split out original parameters
277    $id = $data['id'];
278    $Indexer = idx_get_indexer();
279    $parsedQuery = ft_queryParser($Indexer, $id);
280    if (count($parsedQuery['ns']) > 0) {
281        $ns = cleanID($parsedQuery['ns'][0]) . ':';
282        $id = implode(' ', $parsedQuery['highlight']);
283    }
284    if (count($parsedQuery['notns']) > 0) {
285        $notns = cleanID($parsedQuery['notns'][0]) . ':';
286        $id = implode(' ', $parsedQuery['highlight']);
287    }
288
289    $in_ns    = $data['in_ns'];
290    $in_title = $data['in_title'];
291    $cleaned = cleanID($id);
292
293    $Indexer = idx_get_indexer();
294    $page_idx = $Indexer->getPages();
295
296    $pages = [];
297    if ($id !== '' && $cleaned !== '') {
298        foreach ($page_idx as $p_id) {
299            if ((strpos($in_ns ? $p_id : noNSorNS($p_id), $cleaned) !== false)) {
300                if (!isset($pages[$p_id]))
301                    $pages[$p_id] = p_get_first_heading($p_id, METADATA_DONT_RENDER);
302            }
303        }
304        if ($in_title) {
305            foreach ($Indexer->lookupKey('title', $id, '_ft_pageLookupTitleCompare') as $p_id) {
306                if (!isset($pages[$p_id]))
307                    $pages[$p_id] = p_get_first_heading($p_id, METADATA_DONT_RENDER);
308            }
309        }
310    }
311
312    if (isset($ns)) {
313        foreach (array_keys($pages) as $p_id) {
314            if (strpos($p_id, $ns) !== 0) {
315                unset($pages[$p_id]);
316            }
317        }
318    }
319    if (isset($notns)) {
320        foreach (array_keys($pages) as $p_id) {
321            if (strpos($p_id, $notns) === 0) {
322                unset($pages[$p_id]);
323            }
324        }
325    }
326
327    // discard hidden pages
328    // discard nonexistent pages
329    // check ACL permissions
330    foreach (array_keys($pages) as $idx) {
331        if (
332            !isVisiblePage($idx) || !page_exists($idx) ||
333            auth_quickaclcheck($idx) < AUTH_READ
334        ) {
335            unset($pages[$idx]);
336        }
337    }
338
339    $pages = _ft_filterResultsByTime($pages, $data['after'], $data['before']);
340
341    uksort($pages, 'ft_pagesorter');
342    return $pages;
343}
344
345
346/**
347 * @param array      $results search results in the form pageid => value
348 * @param int|string $after   only returns results with mtime after this date, accepts timestap or strtotime arguments
349 * @param int|string $before  only returns results with mtime after this date, accepts timestap or strtotime arguments
350 *
351 * @return array
352 */
353function _ft_filterResultsByTime(array $results, $after, $before)
354{
355    if ($after || $before) {
356        $after = is_int($after) ? $after : strtotime($after);
357        $before = is_int($before) ? $before : strtotime($before);
358
359        foreach (array_keys($results) as $id) {
360            $mTime = filemtime(wikiFN($id));
361            if ($after && $after > $mTime) {
362                unset($results[$id]);
363                continue;
364            }
365            if ($before && $before < $mTime) {
366                unset($results[$id]);
367            }
368        }
369    }
370
371    return $results;
372}
373
374/**
375 * Tiny helper function for comparing the searched title with the title
376 * from the search index. This function is a wrapper around stripos with
377 * adapted argument order and return value.
378 *
379 * @param string $search searched title
380 * @param string $title  title from index
381 * @return bool
382 */
383function _ft_pageLookupTitleCompare($search, $title)
384{
385    if (Clean::isASCII($search)) {
386        $pos = stripos($title, $search);
387    } else {
388        $pos = PhpString::strpos(
389            PhpString::strtolower($title),
390            PhpString::strtolower($search)
391        );
392    }
393
394    return $pos !== false;
395}
396
397/**
398 * Sort pages based on their namespace level first, then on their string
399 * values. This makes higher hierarchy pages rank higher than lower hierarchy
400 * pages.
401 *
402 * @param string $a
403 * @param string $b
404 * @return int Returns < 0 if $a is less than $b; > 0 if $a is greater than $b, and 0 if they are equal.
405 */
406function ft_pagesorter($a, $b)
407{
408    $ac = count(explode(':', $a));
409    $bc = count(explode(':', $b));
410    if ($ac < $bc) {
411        return -1;
412    } elseif ($ac > $bc) {
413        return 1;
414    }
415    return Sort::strcmp($a, $b);
416}
417
418/**
419 * Sort pages by their mtime, from newest to oldest
420 *
421 * @param string $a
422 * @param string $b
423 *
424 * @return int Returns < 0 if $a is newer than $b, > 0 if $b is newer than $a and 0 if they are of the same age
425 */
426function ft_pagemtimesorter($a, $b)
427{
428    $mtimeA = filemtime(wikiFN($a));
429    $mtimeB = filemtime(wikiFN($b));
430    return $mtimeB - $mtimeA;
431}
432
433/**
434 * Creates a snippet extract
435 *
436 * @author Andreas Gohr <andi@splitbrain.org>
437 * @triggers FULLTEXT_SNIPPET_CREATE
438 *
439 * @param string $id page id
440 * @param array $highlight
441 * @return mixed
442 */
443function ft_snippet($id, $highlight)
444{
445    $text = rawWiki($id);
446    $text = str_replace("\xC2\xAD", '', $text);
447     // remove soft-hyphens
448    $evdata = [
449        'id'        => $id,
450        'text'      => &$text,
451        'highlight' => &$highlight,
452        'snippet'   => ''
453    ];
454
455    $evt = new Event('FULLTEXT_SNIPPET_CREATE', $evdata);
456    if ($evt->advise_before()) {
457        $match = [];
458        $snippets = [];
459        $utf8_offset = 0;
460        $offset = 0;
461        $end = 0;
462        $len = PhpString::strlen($text);
463
464        // build a regexp from the phrases to highlight
465        $re1 = '(' .
466            implode(
467                '|',
468                array_map(
469                    'ft_snippet_re_preprocess',
470                    array_map(
471                        'preg_quote_cb',
472                        array_filter((array) $highlight)
473                    )
474                )
475            ) .
476            ')';
477        $re2 = "$re1.{0,75}(?!\\1)$re1";
478        $re3 = "$re1.{0,45}(?!\\1)$re1.{0,45}(?!\\1)(?!\\2)$re1";
479
480        for ($cnt = 4; $cnt--;) {
481            if (0) {
482            } elseif (preg_match('/' . $re3 . '/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
483            } elseif (preg_match('/' . $re2 . '/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
484            } elseif (preg_match('/' . $re1 . '/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
485            } else {
486                break;
487            }
488
489            [$str, $idx] = $match[0];
490
491            // convert $idx (a byte offset) into a utf8 character offset
492            $utf8_idx = PhpString::strlen(substr($text, 0, $idx));
493            $utf8_len = PhpString::strlen($str);
494
495            // establish context, 100 bytes surrounding the match string
496            // first look to see if we can go 100 either side,
497            // then drop to 50 adding any excess if the other side can't go to 50,
498            $pre = min($utf8_idx - $utf8_offset, 100);
499            $post = min($len - $utf8_idx - $utf8_len, 100);
500
501            if ($pre > 50 && $post > 50) {
502                $pre = 50;
503                $post = 50;
504            } elseif ($pre > 50) {
505                $pre = min($pre, 100 - $post);
506            } elseif ($post > 50) {
507                $post = min($post, 100 - $pre);
508            } elseif ($offset == 0) {
509                // both are less than 50, means the context is the whole string
510                // make it so and break out of this loop - there is no need for the
511                // complex snippet calculations
512                $snippets = [$text];
513                break;
514            }
515
516            // establish context start and end points, try to append to previous
517            // context if possible
518            $start = $utf8_idx - $pre;
519            $append = ($start < $end) ? $end : false;  // still the end of the previous context snippet
520            $end = $utf8_idx + $utf8_len + $post;      // now set it to the end of this context
521
522            if ($append) {
523                $snippets[count($snippets) - 1] .= PhpString::substr($text, $append, $end - $append);
524            } else {
525                $snippets[] = PhpString::substr($text, $start, $end - $start);
526            }
527
528            // set $offset for next match attempt
529            // continue matching after the current match
530            // if the current match is not the longest possible match starting at the current offset
531            // this prevents further matching of this snippet but for possible matches of length
532            // smaller than match length + context (at least 50 characters) this match is part of the context
533            $utf8_offset = $utf8_idx + $utf8_len;
534            $offset = $idx + strlen(PhpString::substr($text, $utf8_idx, $utf8_len));
535            $offset = Clean::correctIdx($text, $offset);
536        }
537
538        $m = "\1";
539        $snippets = preg_replace('/' . $re1 . '/iu', $m . '$1' . $m, $snippets);
540        $snippet = preg_replace(
541            '/' . $m . '([^' . $m . ']*?)' . $m . '/iu',
542            '<strong class="search_hit">$1</strong>',
543            hsc(implode('... ', $snippets))
544        );
545
546        $evdata['snippet'] = $snippet;
547    }
548    $evt->advise_after();
549    unset($evt);
550
551    return $evdata['snippet'];
552}
553
554/**
555 * Wraps a search term in regex boundary checks.
556 *
557 * @param string $term
558 * @return string
559 */
560function ft_snippet_re_preprocess($term)
561{
562    // do not process asian terms where word boundaries are not explicit
563    if (Asian::isAsianWords($term)) return $term;
564
565    if (UTF8_PROPERTYSUPPORT) {
566        // unicode word boundaries
567        // see http://stackoverflow.com/a/2449017/172068
568        $BL = '(?<!\pL)';
569        $BR = '(?!\pL)';
570    } else {
571        // not as correct as above, but at least won't break
572        $BL = '\b';
573        $BR = '\b';
574    }
575
576    if (substr($term, 0, 2) == '\\*') {
577        $term = substr($term, 2);
578    } else {
579        $term = $BL . $term;
580    }
581
582    if (substr($term, -2, 2) == '\\*') {
583        $term = substr($term, 0, -2);
584    } else {
585        $term .= $BR;
586    }
587
588    if ($term == $BL || $term == $BR || $term == $BL . $BR) $term = '';
589    return $term;
590}
591
592/**
593 * Combine found documents and sum up their scores
594 *
595 * This function is used to combine searched words with a logical
596 * AND. Only documents available in all arrays are returned.
597 *
598 * based upon PEAR's PHP_Compat function for array_intersect_key()
599 *
600 * @param array $args An array of page arrays
601 * @return array
602 */
603function ft_resultCombine($args)
604{
605    $array_count = count($args);
606    if ($array_count == 1) {
607        return $args[0];
608    }
609
610    $result = [];
611    if ($array_count > 1) {
612        foreach ($args[0] as $key => $value) {
613            $result[$key] = $value;
614            for ($i = 1; $i !== $array_count; $i++) {
615                if (!isset($args[$i][$key])) {
616                    unset($result[$key]);
617                    break;
618                }
619                $result[$key] += $args[$i][$key];
620            }
621        }
622    }
623    return $result;
624}
625
626/**
627 * Unites found documents and sum up their scores
628 *
629 * based upon ft_resultCombine() function
630 *
631 * @param array $args An array of page arrays
632 * @return array
633 *
634 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
635 */
636function ft_resultUnite($args)
637{
638    $array_count = count($args);
639    if ($array_count === 1) {
640        return $args[0];
641    }
642
643    $result = $args[0];
644    for ($i = 1; $i !== $array_count; $i++) {
645        foreach (array_keys($args[$i]) as $id) {
646            $result[$id] += $args[$i][$id];
647        }
648    }
649    return $result;
650}
651
652/**
653 * Computes the difference of documents using page id for comparison
654 *
655 * nearly identical to PHP5's array_diff_key()
656 *
657 * @param array $args An array of page arrays
658 * @return array
659 *
660 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
661 */
662function ft_resultComplement($args)
663{
664    $array_count = count($args);
665    if ($array_count === 1) {
666        return $args[0];
667    }
668
669    $result = $args[0];
670    foreach (array_keys($result) as $id) {
671        for ($i = 1; $i !== $array_count; $i++) {
672            if (isset($args[$i][$id])) unset($result[$id]);
673        }
674    }
675    return $result;
676}
677
678/**
679 * Parses a search query and builds an array of search formulas
680 *
681 * @author Andreas Gohr <andi@splitbrain.org>
682 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
683 *
684 * @param Indexer $Indexer
685 * @param string                  $query search query
686 * @return array of search formulas
687 */
688function ft_queryParser($Indexer, $query)
689{
690    /**
691     * parse a search query and transform it into intermediate representation
692     *
693     * in a search query, you can use the following expressions:
694     *
695     *   words:
696     *     include
697     *     -exclude
698     *   phrases:
699     *     "phrase to be included"
700     *     -"phrase you want to exclude"
701     *   namespaces:
702     *     @include:namespace (or ns:include:namespace)
703     *     ^exclude:namespace (or -ns:exclude:namespace)
704     *   groups:
705     *     ()
706     *     -()
707     *   operators:
708     *     and ('and' is the default operator: you can always omit this)
709     *     or  (or pipe symbol '|', lower precedence than 'and')
710     *
711     * e.g. a query [ aa "bb cc" @dd:ee ] means "search pages which contain
712     *      a word 'aa', a phrase 'bb cc' and are within a namespace 'dd:ee'".
713     *      this query is equivalent to [ -(-aa or -"bb cc" or -ns:dd:ee) ]
714     *      as long as you don't mind hit counts.
715     *
716     * intermediate representation consists of the following parts:
717     *
718     *   ( )           - group
719     *   AND           - logical and
720     *   OR            - logical or
721     *   NOT           - logical not
722     *   W+:, W-:, W_: - word      (underscore: no need to highlight)
723     *   P+:, P-:      - phrase    (minus sign: logically in NOT group)
724     *   N+:, N-:      - namespace
725     */
726    $parsed_query = '';
727    $parens_level = 0;
728    $terms = preg_split(
729        '/(-?".*?")/u',
730        PhpString::strtolower($query),
731        -1,
732        PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY
733    );
734
735    foreach ($terms as $term) {
736        $parsed = '';
737        if (preg_match('/^(-?)"(.+)"$/u', $term, $matches)) {
738            // phrase-include and phrase-exclude
739            $not = $matches[1] ? 'NOT' : '';
740            $parsed = $not . ft_termParser($Indexer, $matches[2], false, true);
741        } else {
742            // fix incomplete phrase
743            $term = str_replace('"', ' ', $term);
744
745            // fix parentheses
746            $term = str_replace(')', ' ) ', $term);
747            $term = str_replace('(', ' ( ', $term);
748            $term = str_replace('- (', ' -(', $term);
749
750            // treat pipe symbols as 'OR' operators
751            $term = str_replace('|', ' or ', $term);
752
753            // treat ideographic spaces (U+3000) as search term separators
754            // FIXME: some more separators?
755            $term = preg_replace('/[ \x{3000}]+/u', ' ', $term);
756            $term = trim($term);
757            if ($term === '') continue;
758
759            $tokens = explode(' ', $term);
760            foreach ($tokens as $token) {
761                if ($token === '(') {
762                    // parenthesis-include-open
763                    $parsed .= '(';
764                    ++$parens_level;
765                } elseif ($token === '-(') {
766                    // parenthesis-exclude-open
767                    $parsed .= 'NOT(';
768                    ++$parens_level;
769                } elseif ($token === ')') {
770                    // parenthesis-any-close
771                    if ($parens_level === 0) continue;
772                    $parsed .= ')';
773                    $parens_level--;
774                } elseif ($token === 'and') {
775                    // logical-and (do nothing)
776                } elseif ($token === 'or') {
777                    // logical-or
778                    $parsed .= 'OR';
779                } elseif (preg_match('/^(?:\^|-ns:)(.+)$/u', $token, $matches)) {
780                    // namespace-exclude
781                    $parsed .= 'NOT(N+:' . $matches[1] . ')';
782                } elseif (preg_match('/^(?:@|ns:)(.+)$/u', $token, $matches)) {
783                    // namespace-include
784                    $parsed .= '(N+:' . $matches[1] . ')';
785                } elseif (preg_match('/^-(.+)$/', $token, $matches)) {
786                    // word-exclude
787                    $parsed .= 'NOT(' . ft_termParser($Indexer, $matches[1]) . ')';
788                } else {
789                    // word-include
790                    $parsed .= ft_termParser($Indexer, $token);
791                }
792            }
793        }
794        $parsed_query .= $parsed;
795    }
796
797    // cleanup (very sensitive)
798    $parsed_query .= str_repeat(')', $parens_level);
799    do {
800        $parsed_query_old = $parsed_query;
801        $parsed_query = preg_replace('/(NOT)?\(\)/u', '', $parsed_query);
802    } while ($parsed_query !== $parsed_query_old);
803    $parsed_query = preg_replace('/(NOT|OR)+\)/u', ')', $parsed_query);
804    $parsed_query = preg_replace('/(OR)+/u', 'OR', $parsed_query);
805    $parsed_query = preg_replace('/\(OR/u', '(', $parsed_query);
806    $parsed_query = preg_replace('/^OR|OR$/u', '', $parsed_query);
807    $parsed_query = preg_replace('/\)(NOT)?\(/u', ')AND$1(', $parsed_query);
808
809    // adjustment: make highlightings right
810    $parens_level     = 0;
811    $notgrp_levels    = [];
812    $parsed_query_new = '';
813    $tokens = preg_split('/(NOT\(|[()])/u', $parsed_query, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
814    foreach ($tokens as $token) {
815        if ($token === 'NOT(') {
816            $notgrp_levels[] = ++$parens_level;
817        } elseif ($token === '(') {
818            ++$parens_level;
819        } elseif ($token === ')') {
820            if ($parens_level-- === end($notgrp_levels)) array_pop($notgrp_levels);
821        } elseif (count($notgrp_levels) % 2 === 1) {
822            // turn highlight-flag off if terms are logically in "NOT" group
823            $token = preg_replace('/([WPN])\+\:/u', '$1-:', $token);
824        }
825        $parsed_query_new .= $token;
826    }
827    $parsed_query = $parsed_query_new;
828
829    /**
830     * convert infix notation string into postfix (Reverse Polish notation) array
831     * by Shunting-yard algorithm
832     *
833     * see: http://en.wikipedia.org/wiki/Reverse_Polish_notation
834     * see: http://en.wikipedia.org/wiki/Shunting-yard_algorithm
835     */
836    $parsed_ary     = [];
837    $ope_stack      = [];
838    $ope_precedence = [')' => 1, 'OR' => 2, 'AND' => 3, 'NOT' => 4, '(' => 5];
839    $ope_regex      = '/([()]|OR|AND|NOT)/u';
840
841    $tokens = preg_split($ope_regex, $parsed_query, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
842    foreach ($tokens as $token) {
843        if (preg_match($ope_regex, $token)) {
844            // operator
845            $last_ope = end($ope_stack);
846            while ($last_ope !== false && $ope_precedence[$token] <= $ope_precedence[$last_ope] && $last_ope != '(') {
847                $parsed_ary[] = array_pop($ope_stack);
848                $last_ope = end($ope_stack);
849            }
850            if ($token == ')') {
851                array_pop($ope_stack); // this array_pop always deletes '('
852            } else {
853                $ope_stack[] = $token;
854            }
855        } else {
856            // operand
857            $token_decoded = str_replace(['OP', 'CP'], ['(', ')'], $token);
858            $parsed_ary[] = $token_decoded;
859        }
860    }
861    $parsed_ary = array_values([...$parsed_ary, ...array_reverse($ope_stack)]);
862
863    // cleanup: each double "NOT" in RPN array actually does nothing
864    $parsed_ary_count = count($parsed_ary);
865    for ($i = 1; $i < $parsed_ary_count; ++$i) {
866        if ($parsed_ary[$i] === 'NOT' && $parsed_ary[$i - 1] === 'NOT') {
867            unset($parsed_ary[$i], $parsed_ary[$i - 1]);
868        }
869    }
870    $parsed_ary = array_values($parsed_ary);
871
872    // build return value
873    $q = [];
874    $q['query']      = $query;
875    $q['parsed_str'] = $parsed_query;
876    $q['parsed_ary'] = $parsed_ary;
877
878    foreach ($q['parsed_ary'] as $token) {
879        if (strlen($token) < 3 || $token[2] !== ':') continue;
880        $body = substr($token, 3);
881
882        switch (substr($token, 0, 3)) {
883            case 'N+:':
884                     $q['ns'][]        = $body; // for backward compatibility
885                break;
886            case 'N-:':
887                     $q['notns'][]     = $body; // for backward compatibility
888                break;
889            case 'W_:':
890                     $q['words'][]     = $body;
891                break;
892            case 'W-:':
893                     $q['words'][]     = $body;
894                     $q['not'][]       = $body; // for backward compatibility
895                break;
896            case 'W+:':
897                     $q['words'][]     = $body;
898                     $q['highlight'][] = $body;
899                     $q['and'][]       = $body; // for backward compatibility
900                break;
901            case 'P-:':
902                     $q['phrases'][]   = $body;
903                break;
904            case 'P+:':
905                     $q['phrases'][]   = $body;
906                     $q['highlight'][] = $body;
907                break;
908        }
909    }
910    foreach (['words', 'phrases', 'highlight', 'ns', 'notns', 'and', 'not'] as $key) {
911        $q[$key] = empty($q[$key]) ? [] : array_values(array_unique($q[$key]));
912    }
913
914    return $q;
915}
916
917/**
918 * Transforms given search term into intermediate representation
919 *
920 * This function is used in ft_queryParser() and not for general purpose use.
921 *
922 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
923 *
924 * @param Indexer $Indexer
925 * @param string                  $term
926 * @param bool                    $consider_asian
927 * @param bool                    $phrase_mode
928 * @return string
929 */
930function ft_termParser($Indexer, $term, $consider_asian = true, $phrase_mode = false)
931{
932    $parsed = '';
933    if ($consider_asian) {
934        // successive asian characters need to be searched as a phrase
935        $words = Asian::splitAsianWords($term);
936        foreach ($words as $word) {
937            $phrase_mode = $phrase_mode ? true : Asian::isAsianWords($word);
938            $parsed .= ft_termParser($Indexer, $word, false, $phrase_mode);
939        }
940    } else {
941        $term_noparen = str_replace(['(', ')'], ' ', $term);
942        $words = $Indexer->tokenizer($term_noparen, true);
943
944        // W_: no need to highlight
945        if (empty($words)) {
946            $parsed = '()'; // important: do not remove
947        } elseif ($words[0] === $term) {
948            $parsed = '(W+:' . $words[0] . ')';
949        } elseif ($phrase_mode) {
950            $term_encoded = str_replace(['(', ')'], ['OP', 'CP'], $term);
951            $parsed = '((W_:' . implode(')(W_:', $words) . ')(P+:' . $term_encoded . '))';
952        } else {
953            $parsed = '((W+:' . implode(')(W+:', $words) . '))';
954        }
955    }
956    return $parsed;
957}
958
959/**
960 * Recreate a search query string based on parsed parts, doesn't support negated phrases and `OR` searches
961 *
962 * @param array $and
963 * @param array $not
964 * @param array $phrases
965 * @param array $ns
966 * @param array $notns
967 *
968 * @return string
969 */
970function ft_queryUnparser_simple(array $and, array $not, array $phrases, array $ns, array $notns)
971{
972    $query = implode(' ', $and);
973    if ($not !== []) {
974        $query .= ' -' . implode(' -', $not);
975    }
976
977    if ($phrases !== []) {
978        $query .= ' "' . implode('" "', $phrases) . '"';
979    }
980
981    if ($ns !== []) {
982        $query .= ' @' . implode(' @', $ns);
983    }
984
985    if ($notns !== []) {
986        $query .= ' ^' . implode(' ^', $notns);
987    }
988
989    return $query;
990}
991
992//Setup VIM: ex: et ts=4 :
993